题目描述

求一个满足 $k$ 阶齐次线性递推数列 ${a_i}$ 的第 $n$ 项，即：

输入格式

第一行两个数 $n$,$k$，如题面所述。

第二行 $k$ 个数，表示 $f_1 \ f_2 \ \cdots \ f_k$

第三行 $k$ 个数，表示 $a_0 \ a_1 \ \cdots \ a_{k-1}$

输出格式

一个数，表示 $a_n \bmod 998244353$ 的值

6 4
3 -1 0 4
-2 3 1 5

73

提示

$N = 10^{9} , K = 32000$

保证读入的数字均为 $[-10^9,10^9]$ 内的整数。