P4723 [Template] Constant-Coefficient Homogeneous Linear Recurrence.

Find the $n$-th term of a $k$-th order homogeneous linear recurrence sequence $\{a_i\}$, that is: $$a_n=\sum\limits_{i=1}^{k}f_i \times a_{n-i}$$

The first line contains two integers $n$ and $k$, as described in the statement. The second line contains $k$ integers, representing $f_1 \ f_2 \ \cdots \ f_k$. The third line contains $k$ integers, representing $a_0 \ a_1 \ \cdots \ a_{k-1}$.

Output one integer, the value of $a_n \bmod 998244353$.

Constraints: $N = 10^{9}$, $K = 32000$. It is guaranteed that all input numbers are integers in the range $[-10^9,10^9]$. Translated by ChatGPT 5