問題
長さ N の整数列 A が与えられます。
正整数 x に関する関数 f(x) を次のように定義します。
- f(x)={Ax( if1≤x≤N )f(x−1)+f(x−2)+…+f(x−N)( ifx≥N+1 )
f(X) を 998244353 で割った余りを求めてください。
制約
- 1≤N≤2×105
- 1≤X≤5×105
- 0≤Ai≤998244352(1≤i≤N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
サンプル 1
このような計算をすれば答えを求めることができます。
- f(1)=A1=1
- f(2)=A2=1
- f(3)=f(2)+f(1)=2
- f(4)=f(3)+f(2)=3
- f(5)=f(4)+f(3)=5
よって、答えは 5 となります。
サンプル 2
入力2
15 10000
806413653 500940409 485353637 91489265 310431898 771043380 712137305 711436923 575371013 800850108 251980687 446868718 772636473 949053376 619975694
998244353 で割った余りを求めてください。