MEX 计数

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

对于一个非负整数数组 $c$，定义 $\operatorname{MEX}(c)$ 为没有在 $c$ 中出现的最小非负整数。例如，$\operatorname{MEX}([0,1,3])=2$，$\operatorname{MEX}([42])=0$。

给定整数 $n,k$ 和数组 $b_1,b_2,\ldots,b_n$。求有多少个数组 $a_1,a_2,\ldots,a_n$ 同时满足：

• 对每个 $1\le i\le n$，都有 $0\le a_i\le n$；
• 对每个 $1\le i\le n$，都有$$\left|\operatorname{MEX}([a_1,a_2,\ldots,a_i])-b_i\right|\le k.$$

答案可能很大，请输出其对 $998\,244\,353$ 取模后的结果。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

输出格式

输出一个整数，表示满足条件的数组个数对 $998\,244\,353$ 取模后的结果。

样例输入 1

4 0
0 0 0 0

样例输出 1

256

样例输入 2

4 1
0 0 0 0

样例输出 2

431

样例输入 3

4 1
0 0 1 1

样例输出 3

509

样例输入 4

5 2
0 0 2 2 0

样例输出 4

6546

样例输入 5

3 2
-2 0 4

样例输出 5

11

数据范围

对于所有数据：

• $1\le n\le 2000$；
• $0\le k\le 50$；
• $-k\le b_i\le n+k$。

每个测试点独立计分。

说明

本题中的所有下标均从 $1$ 开始。每个位置的 $a_i$ 都可以独立取 $0,1,\ldots,n$ 中的任意一个整数。