← 返回题目列表

Codeforces · 1608/F

F. MEX 计数

中文机器翻译题面 查看原题

对于非负整数数组 $$$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