题目描述

定义 $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$。

输出格式

一行一个整数表示答案。

10 25
-5 -73 -95 64 15
-80 -31 -58 15 95 -1 14 -30 31 

998096342

提示

$\textbf{Subtask}$	$k \leq$	$n \leq$	特殊性质	分值
$1$	$100$	$100$	无	$5$
$2$		$2^{63}$		$25$
$3$	$5000$		$s = 1, \forall 2 \leq i \leq k, t_i = 1$	$10$
$4$			无	$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$。