Problem Description

Find the $n$-th term of a $k$-th order homogeneous linear recurrence sequence $\{a_i\}$, that is:

Input Format

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 Format

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

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

73

Hint

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