P8979 "DTOI-4" White Fibonacci.

Define $F(k, n)$ as follows: $$ 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. $$ Given the coefficients in the recurrence of $F$ and $k, n$, compute the value of $F(k, n) \bmod 998244353$.

The first line contains two integers $k, n$. The second line contains five integers $st_0, st_1, a, b, s$. The third line contains $k - 1$ integers $t_2, t_3, \cdots, t_k$.

Output one integer on a single line, which is the answer.

| $\textbf{Subtask}$ | $k \leq$ | $n \leq$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | $100$ | None | $5$ | | $2$ | $100$ | $2^{63}$ | None | $25$ | | $3$ | $5000$ | $2^{63}$ | $s = 1, \forall 2 \leq i \leq k, t_i = 1$ | $10$ | | $4$ | $5000$ | $2^{63}$ | None | $60$ | For $100\%$ of the testdata, $1 \leq k \leq 5 \times 10^3$, $0 \leq n \le 2^{63}$, and $-998244352 \leq st_0, st_1, a, b, s, t_i \leq 998244352$. Translated by ChatGPT 5