P6115 【模板】整式递推

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

无

无

【样例一解释】 这里的递推式就是 $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