【模板】整式递推

题目背景

话说上次菜菜的 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$ 的系数。

输出格式


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

输入输出样例

输入样例 #1

5 2 1
1 0
998244352 0
998244352 1
998244352 1

输出样例 #1

44

输入样例 #2

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

输出样例 #2

193416411

输入样例 #3

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

输出样例 #3

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