对于非负整数数组 $$$c$$$,$$$MEX(c)$$$ 表示其中未出现的最小非负整数。例如,$$$MEX([0, 1, 3]) = 2$$$,$$$MEX([42]) = 0$$$。
给定整数 $$$n、k$$$ 和数组 $$$[b_1, b_2, \ldots, b_n]$$$。
求满足以下条件的数组 $$$[a_1, a_2, \ldots, a_n]$$$ 的数量:
- $$$0 \le a_i \le n$$$ 对于每个 $$$i$$$ 对于每个 $$$i$$$ 从 $$$1$$$ 到 $$$n$$$。
- $$$|MEX([a_1, a_2, \ldots, a_i]) - b_i| \le k$$$ 对于从$$$1$$$ 到$$$n$$$ 的每个$$$i$$$。
由于这个数字可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。
输入
输入的第一行包含两个整数 $$$n, k$$$ ($$$1 \le n \le 2000$$$, $$$0 \le k \le 50$$$)。
输入的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$-k \le b_i \le n+k$$$) — 数组 $$$b$$$ 的元素。
输出
输出一个整数 - 满足语句条件的数组数量,以 $$$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