189 q-整式递推

这是一道模板题。

对于无限数列 ${a}{n=0}^\infty$，已知 $\forall n \ge m$ 都满足 $$\sum P_k(q^n) = 0$$ 其中 $P_k$ 为不超过 $d$ 次的多项式，$q$ 是给定的常数。}^m a_{n-k
给定所有 $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$ 的系数。

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

样例 $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}$