問題文

長さ NN の整数列 A=(A1,A2,,AN)A=(A_1,A_2,\dots,A_N ) が与えられます。
整数 xx非負整数 yy に対して関数 f(x,y)f(x,y) は以下のように定義されます。

{f(x,y)=f(x+a,y1)+f(x+b,y1)(y0)f(x,y)=Ax(1xN,y=0)f(x,y)=0(otherwise)\left\{ \begin{array}{ll} f(x,y)=f(x+a,y-1)+f(x+b,y-1) & (y≠0) \\ f(x,y)=A_x & (1 \leq x \leq N,y=0) \\ f(x,y)=0 & (\text{otherwise}) \end{array} \right.

このとき、f(l,M)+f(l+1,M)++f(l+N1,M)f(l,M)+f(l+1,M)+ \dots +f(l+N-1,M) の値を求めて下さい。 ただし、答えは非常に大きくなる場合があるので、998244353998244353 で割った余りを求めて下さい。

制約

  • 入力される値は全て整数である。
  • 1N,M2×1051 \leq N,M \leq 2×10^5
  • 0a,b,A[i],l1090 \leq |a|,|b|,|A[i]|,|l| \leq 10^{9}
  • aba≠b

入力

入力は以下の形式で標準入力から与えられる。

NNMMllaabb
A1A_1A2A_2......ANA_N

出力

答えを一行に出力して、最後に改行せよ。

サンプル

入力1
2 1 1 1 -1
1 2
出力1
3

f(1,1)+f(2,1)=f(2,0)+f(0,0)+f(3,0)+f(1,0)=2+0+0+1=3f(1,1)+f(2,1)=f(2,0)+f(0,0)+f(3,0)+f(1,0)=2+0+0+1=3 です。

入力2
2 5 1 1 -1
1 2
出力2
30
入力3
5 5 1 1 -2
3 1 4 1 5
出力3
170
入力4
7 314 15 9 -2
6 5 3 5 8 9 7
出力4
45643497

Submit


Go (1.21)