B - Nbonacci Sequence

問題

長さ $N$ の整数列 $A$ が与えられます。
正整数 $x$ に関する関数 $f(x)$ を次のように定義します。

• $\displaystyle f(x) = \begin{cases} A_x \enspace ( \ \mathrm{if} \enspace 1 \leq x \leq N \ ) \\ f(x-1) + f(x-2) + \ldots + f(x-N) \enspace ( \ \mathrm{if} \enspace x \geq N+1 \ ) \end{cases}$

$f(X)$ を $998244353$ で割った余りを求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq X \leq 5 \times 10^5$
• $0 \leq A_i \leq 998244352 \enspace (1 \leq i \leq N)$
• 入力はすべて整数

入力

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

出力

答えを出力せよ。

サンプル 1

2 5
1 1

5

このような計算をすれば答えを求めることができます。

• $f(1) = A_1 = 1$
• $f(2) = A_2 = 1$
• $f(3) = f(2) + f(1) = 2$
• $f(4) = f(3) + f(2) = 3$
• $f(5) = f(4) + f(3) = 5$

よって、答えは $5$ となります。

サンプル 2

15 10000
806413653 500940409 485353637 91489265 310431898 771043380 712137305 711436923 575371013 800850108 251980687 446868718 772636473 949053376 619975694

846683190

$998244353$ で割った余りを求めてください。