题目背景

话说上次菜菜的 NaCly_Fish 想教后辈做常系数线性齐次递推，奈何智商不够，见识短浅，被机房同学轮番吊打。

之后她又听说了整式递推这种东西，便去请教中国队长 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$。然而 $\mathsf E \color{red}\mathsf{ntropyIncreaser}$ 觉得这个东西太简单了，只回应了一句：“你不看候选队论文么？”

NaCly_Fish 终于找来论文，但她完全看不懂。于是她只能找又强又热心的你来教她这个问题。

题目描述

对于无限数列 $a$，已知 $\forall n \ge m$ 都满足

其中 $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