「DTOI-4」白的 Fibonacci
题目描述
定义 $F(k, n)$ 如下：
$$
F(k,n) =
\left \{
\begin{aligned}
&st_0\ && k = 1\ \land\ n = 0 \\
&st_1\ && k = 1\ \land\ n = 1 \\
&0\ && k > 1 \ \land \ n < 0 \\
&a \times F(k, n - 1) + b \times F(k, n - 2)\ && k = 1 \ \land\ n > 1 \\
&t_k \times F(k, n - 1) + s^n \times F(k - 1, n)\ && \text{otherwise}
\end{aligned}
\right.
$$
给定 $F$ 递推式的各项系数和 $k, n$，请你求出 $F(k, n) \bmod 998244353$ 的值。
输入输出格式
输入格式
第一行，两个整数 $k, n$；
第二行，五个整数 $st_0, st_1, a, b, s$；
第三行，$k - 1$ 个整数 $t_2, t_3, \cdots, t_k$。
输出格式
一行一个整数表示答案。
输入输出样例
输入样例 #1
10 25
-5 -73 -95 64 15
-80 -31 -58 15 95 -1 14 -30 31 输出样例 #1
998096342说明
| $\textbf{Subtask}$ | $k \leq$ | $n \leq$ | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $100$ | $100$ | 无 | $5$ |
| $2$ | $100$ | $2^{63}$ | 无 | $25$ |
| $3$ | $5000$ | $2^{63}$ | $s = 1, \forall 2 \leq i \leq k, t_i = 1$ | $10$ |
| $4$ | $5000$ | $2^{63}$ | 无 | $60$ |
对于 $100\%$ 的数据，$1 \leq k \leq 5 \times 10^3$，$0 \leq n \le 2^{63}$，$-998244352 \leq st_0, st_1, a, b, s, t_i \leq 998244352$。