Description

Given the recurrence:

where $P(x)$ is a polynomial of degree $m$.

Given $f_1,f_2,\dots,f_k$, $a_0,a_1,\dots,a_{k-1}$, and the coefficients of $P(x)$, find $a_n$.
Output the answer modulo $998244353$.

Input Format

The first line contains three positive integers $n,m,k$.
The second line contains $k$ integers, representing $a_0,a_1,\dots,a_{k-1}$.
The third line contains $k$ integers, representing $f_1,f_2,\dots,f_k$.
The fourth line contains $m+1$ integers, from low degree to high degree, representing the coefficients of $P(x)$.

Output Format

Output one line with one integer, representing the answer.

40 5 6
1 2 3 5 8 13
1 3 4 9 6 7
1 1 4 5 1 4

349344375

Hint

Constraints
For $100\%$ of the testdata, $1\le n \le 10^9$, $1\le m,k \le 30000$.
Except for the first line, all input numbers are in the range $[0,998244353)$.

The testdata has multiple difficulty levels.

Translated by ChatGPT 5