[AdditionalFile189.zip](file://AdditionalFile189.zip?type=additional_file)

#189. q-整式递推

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB 通过: 8 | 提交: 19

题目描述

这是一道模板题。

对于无限数列 $\{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$ 的系数。

输出格式

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

样例

输入

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 \times 3^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}$