Evaluating a Custom Recurrence Function F(k, n) modulo 998244353

You are given a function \(F(k,n)\) defined by the recurrence:

[ F(k,n) = \begin{cases} ; st_0, &\text{if } k = 1 \text{ and } n = 0,\ ; st_1, &\text{if } k = 1 \text{ and } n = 1,\ ; 0, &\text{if } k > 1 \text{ and } n < 0,\ ; a \times F(1, n-1) + b \times F(1, n-2), &\text{if } k = 1 \text{ and } n > 1,\ ; t_k \times F(k, n-1) + s^n \times F(k-1, n), &\text{otherwise.} \end{cases} ]

Your task is to compute \(F(k,n) \bmod 998244353\) given the coefficients and parameters.

Note: All coefficients and parameters are provided as input. When \(k = 1\), the recurrence uses the coefficients \(st_0, st_1, a, b\). For \(k > 1\), additional coefficients \(t_2, t_3, \dots, t_k\) are provided (note: \(t_1\) is not used).

inputFormat

The input consists of the following:

• The first line contains two integers \(k\) and \(n\).
• The second line contains five integers: \(st_0\), \(st_1\), \(a\), \(b\), and \(s\).
• If \(k > 1\), the third line contains \(k-1\) integers: \(t_2, t_3, \dots, t_k\), separated by spaces.

outputFormat

Output a single integer: the value of \(F(k,n)\) modulo \(998244353\).

sample

1 0
2 3 1 1 2

2