【模板】整式递推

话说上次菜菜的 NaCly\_Fish 想教后辈做常系数线性齐次递推，奈何智商不够，见识短浅，被机房同学轮番吊打。 之后她又听说了整式递推这种东西，便去请教中国队长 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$。然而 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 觉得这个东西太简单了，只回应了一句：“你不看候选队论文么？” NaCly\_Fish 终于找来论文，但她完全看不懂。于是她只能找又强又热心的你来教她这个问题。

对于无限数列 $a$，已知 $\forall n \ge m$ 都满足 $$\sum_{k=0}^m a_{n-k} P_k(n) = 0$$ 其中 $P_k$ 为不超过 $d$ 次的多项式。 给定所有 $P_k$ 的系数，和 $\{ a_i \}_{i=0}^{m-1} $，求 $a_n$。 由于答案可能很大，所以要对 $998244353$ 取模。

第一行三个正整数 $n,m,d$。 第二行 $m$ 个非负整数，表示 $\{ a_i \}_{i=0}^{m-1} $。 接下来 $m+1$ 行，每行 $d+1$ 个非负整数；第 $k+3$ 行由低到高地给出 $P_k$ 的系数。

输出一行一个整数，表示答案。

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

【样例一解释】 这里的递推式就是 $a_n \equiv (n-1)(a_{n-1}+a_{n-2}) \pmod{998244353}$，容易计算得 $a_5 \equiv 44 \pmod{998244353}$。 【数据范围】 对于 $30\%$ 的数据，$1\le n \le 10^6$。 对于 $100\%$ 的数据，$1\le m,d \le 7$，$1 \le n \le 6 \times 10^8$。 所有输入不超过 $6 \times 10^8$。 $\forall x \in [m,n] \cap \mathbb Z \text{ s.t. } P_0(x) \not \equiv 0 \pmod{998244353}$。 欢迎加入 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 粉丝群：747262201