問題文

長さ $N$ の整数列 $A=(A_1,\ A_2,\ \dots ,\ A_N)$ は、任意の $i\ (2\le i \le N)$ に対し $\displaystyle \sum_{k=1}^{i-1}A_{k} \geq A_{i}$ が成り立つとき、「バランスの良い数列」であるといいます。

例えば数列 $(2,\ 1,\ 3,\ 6)$ は「バランスの良い数列」ですが、 $(3,\ 2,\ -2,\ 4)$ は「バランスの良い数列」ではありません。

はじめに整数 $N,K$ と長さ $N$ の整数列 $A=(A_1,\ A_2,\ \dots ,\ A_N)$ が与えられます。

以下の条件をすべて満たすような長さ $N$ の整数列 $B=(B_1,\ B_2,\ \dots ,\ B_N)$ の総数を $998244353$ で割った余りを求めてください。

• すべての $1\le i \le N$ に対し $-K \leq B_i \leq K$ が成り立つ
• 長さ $N$ の「バランスの良い数列」 $C=(C_1,\ C_2,\ \dots,\ C_N)$ であって、すべての $1\le i \le N$ に対し $B_i \leq C_i$ が成り立つもののうち、辞書式順序で最小のものは $A$ である

入力

$N\ K$
$A_1\ A_2\ \dots\ A_N$

• $2 \leq N \leq 10^5$
• $1 \leq K \leq 10^5$
• $-K \leq A_i \leq K\ (1\le i \le N)$
• 与えられる入力はすべて整数
• 与えられる数列 $A$ は「バランスの良い数列」

出力

答えを出力してください。

最後に改行してください。

サンプル

3 1
1 0 1

6

13 600
2 1 3 6 4 16 32 64 -53 75 150 300 600

698798218