F. MEX подсчет
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$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$$$ для каждого $$$i$$$ от $$$1$$$ до $$$n$$$.

Поскольку это число может быть очень большим, выведите его по модулю $$$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$$$.

Примеры
Входные данные
4 0
0 0 0 0
Выходные данные
256
Входные данные
4 1
0 0 0 0
Выходные данные
431
Входные данные
4 1
0 0 1 1
Выходные данные
509
Входные данные
5 2
0 0 2 2 0
Выходные данные
6546
Входные данные
3 2
-2 0 4
Выходные данные
11