Background

Last time, Caicai’s NaCly_Fish wanted to teach her juniors how to do constant-coefficient linear homogeneous recurrences, but her IQ was not enough and her experience was limited, so she got beaten up by her classmates in the lab one after another.

After that, she heard about something called polynomial recurrences, so she went to ask Captain China $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ for advice. However, $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ thought this was too simple and only replied: “Don’t you read the candidate team papers?”

NaCly_Fish finally found the paper, but she could not understand it at all. So she can only ask you, who are strong and enthusiastic, to teach her this problem.

Problem 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