UOJ Logo Zijian Online Judge

ZOJ

#32. 常系数齐次线性递推式

统计

今有一个数列 $A_0, A_1, A_2, \cdots$,它满足这样一个递推式

$$ A_j = \sum_{i=1}^k {B_iA_{j-i}} $$

现在给你 $n$、$k$、$B_1 \sim B_k$ 和 $A_0 \sim A_{k-1}$,请你输出 $A_n$ 对 $998244353$($7 \times 17 \times 2^{23} + 1$,一个质数)取模后的值。

输入格式

第一行两个正整数 $n, k$。

第二行 $k$ 个非负整数表示 $A_0 \sim A_{k-1}$。

第三行 $k$ 个非负整数表示 $B_1 \sim B_k$。

输出格式

一个整数表示答案。

样例一

input

7 2
1 1
1 1

output

21

限制与约定

测试点$n$$k$
$1 \sim 3$$\leq 1000$$\leq 100$
$4 \sim 10$$\leq {10}^9$
$11 \sim 15$$\leq 1000$
$16 \sim 20$$\leq 50000$

对于 $100\%$ 的数据,保证 $1 \le n \le {10}^9,1 \le k \le 5\times {10}^4,0 \le A_0, A_1, \ldots , A_{k-1}, B_1, B_2, \ldots , B_k < 998244353$。

时间限制:$7\texttt{s}$

空间限制:$512\texttt{MB}$