P7132 Little L's Snacks

Little L really likes eating snacks.

**$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**.

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.**

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

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