q-整式递推

题目描述

这是一道模板题。

对于无限数列 $\{a\}_{n=0}^\infty$，已知 $\forall n \ge m$ 都满足

其中 $P_k$ 为不超过 $d$ 次的多项式，$q$ 是给定的常数。
给定所有 $P_k$ 的系数，和 $\{ a_i \}_{i=0}^{m-1}$，求 $a_n$。

答案对 $998244353$ 取模。

输入格式

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

输出格式

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

样例 2

输入

9981274 6 5 3
1 1 4 5 1 4
1 4 7 2 4 2
2 0 8 8 9 2
3 6 9 3 4 1
7 8 2 0 2 3
4 1 3 2 1 5
9 2 3 2 4 8
7 5 2 0 2 3

输出

34764612

说明

样例 $1$ 中给出的数列满足：
$(1+4\times3^n+7\times 9^n)a_n+(2+5\times 3^n+8\times 9^n)a_{n-1}+(3+6\times 3^n+9\times 9^n)a_{n-2}=0$
同时有 $a_0=1$，$a_1=3$，简单计算可得 $a_3= \frac{4949487}{3148048}$，在模 $998244353$ 意义下为 $34997953$。

数据范围与提示

对于 $30\%$ 的数据，$1\le n \le 10^6$；
对于 $100\%$ 的数据，$1\le m,d \le 6$，$1 \le n \le 6 \times 10^8$。

所有输入均不超过 $6 \times 10^8$，保证 $\forall k \in [m,n] \cap \mathbb Z \text{ s.t. } P_0(q^k) \not \equiv 0 \pmod{998244353}$