Description

$O2$ optimization is automatically enabled when submitting.

Little L now wants to put some snacks into a box. However, if the snacks are not stacked steadily, they will fall and break, so Little L wants to find how many stable ways there are to stack snacks.

Each snack can be abstracted as a $1\times1$ square, and the bottom of the box can be seen as a one-dimensional line segment of length $n$. More precisely, the snacks are divided into $n$ piles, placed in the box from left to right, denoted as pile $1,2,\ldots,n$ in order. We consider the height $h_i$ of pile $i$ to be the number of snacks in this pile, and any pile is allowed to contain no snacks.

We define pile $i$ to be stable if and only if:

• $h_i\le m$, i.e. the height of this pile does not exceed $m$.
• While satisfying the previous condition, at least one (or both) of the following conditions holds:
  • $i=1$ or $i=n$. In this case, one side is the inner wall of the box, so this pile will not fall.
  • $\color{red}\max\{h_{i-1},h_{i+1}\}\ge h_i-d_i$. In this case, among the two neighboring piles, at least one is tall enough to support this pile so that it will not fall.

We define a stable way to stack snacks as a sequence $h_i$ of length $n$ such that, when stacking according to this sequence, every pile is stable.

Obviously, the box can hold at most $n\times m$ snacks. We assume Little L has no fewer than $n\times m$ snacks, and it is not necessary to put all snacks into the box. In addition, we assume every snack is exactly the same.

Input Format

There are $2$ lines in total.

The first line contains two positive integers $n,m$.

The second line contains $n$ integers $d_1,d_2\ldots,d_n$, with the meaning as shown in the red part in the Description.

The two numbers on each line are separated by a single space. The testdata is generated on Windows. There may be extra spaces at the end of a line.

Output Format

Print one integer per line, representing the number of stable ways to stack snacks, modulo $998244353$.

3 3
3 1 1 

59

10 13
12 13 1 4 5 9 7 0 3 8 

851695394

Hint

This problem uses the following scoring strategy:
subtask $1$（#$1\sim{}$#$8$）：$10\%$, $n,m\le5$;
subtask $2$（#$9\sim{}$#$12$）：$30\%$, $n,m\le5\times10^2$;
subtask $3$（#$13\sim{}$#$16$）：$20\%$, $n,m\le3\times10^3$;
subtask $4$（#$17\sim{}$#$24$）：$40\%$, $n,m\le7\times10^3$.
For $100\%$ of the testdata: $1\le n,m\le7\times10^3$, $0\le d_i\le m$. You must pass all test points within a subtask to be considered as passing that subtask.

This problem enables subtask dependencies.

Translated by ChatGPT 5