Description

For an infinite sequence $a$, it is known that for all $n \ge m$,

where each $P_k$ is a polynomial of degree at most $d$.
Given the coefficients of all $P_k$, and $\{ a_i \}_{i=0}^{m-1}$, find $a_n$.

Since the answer may be very large, output it modulo $998244353$.

Input Format

The first line contains three positive integers $n, m, d$.
The second line contains $m$ non-negative integers, representing $\{ a_i \}_{i=0}^{m-1}$.
Then there are $m+1$ lines, each containing $d+1$ non-negative integers; line $(k+3)$ gives the coefficients of $P_k$ from low degree to high degree.

Output Format

Output one integer in one line, representing the answer.

5 2 1
1 0
998244352 0
998244352 1
998244352 1

44

233 2 3
1 0
998244352 0 0 0
0 998244349 4 0
0 8 998244337 8

193416411

114514 7 7
1 9 8 2 6 4 7
9 1 8 2 7 6 5 3
2 8 4 6 2 9 4 5
1 9 2 6 0 8 1 7
1 9 1 9 8 1 0 7
1 1 4 5 1 4 4 4
4 4 4 4 4 4 4 4
9 9 8 2 4 4 3 5
1 9 8 6 0 6 0 4

565704112

Hint

[Explanation of Sample 1]
Here the recurrence is $a_n \equiv (n-1)(a_{n-1}+a_{n-2}) \pmod{998244353}$. It is easy to compute that $a_5 \equiv 44 \pmod{998244353}$.

[Constraints]
For $30\%$ of the testdata, $1 \le n \le 10^6$.
For $100\%$ of the testdata, $1 \le m, d \le 7$, $1 \le n \le 6 \times 10^8$.

All inputs are no more than $6 \times 10^8$.
$\forall x \in [m,n] \cap \mathbb Z \text{ s.t. } P_0(x) \not \equiv 0 \pmod{998244353}$.

Welcome to join $\mathsf E \color{red}\mathsf{ntropyIncreaser}$’s fan group: 747262201.

Translated by ChatGPT 5