G. Прогноз
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим турнир, в котором участвуют $$$n$$$ спортсменов. Рейтинг $$$i$$$-го спортсмена равен $$$a_i$$$.

Турнир проходит следующим образом. Сначала каждому спортсмену присваивается индекс — целое число от $$$1$$$ до $$$n$$$. Все индексы различны. Обозначим за $$$p_i$$$ спортсмена с индексом $$$i$$$.

Затем организаторы проведут $$$n-1$$$ игр. В первой игре будут соревноваться спортсмены $$$p_1$$$ и $$$p_2$$$. Во второй — победитель первой игры и спортсмен $$$p_3$$$. В третьей — победитель второй игры и спортсмен $$$p_4$$$, и так далее — в последней игре будут соревноваться победитель игры $$$(n-2)$$$ и спортсмен $$$p_n$$$.

Монокарп хочет спрогнозировать результаты каждой из $$$n-1$$$ игр (конечно, он сформирует свой прогноз только после того, как все спортсмены получат свои индексы). Он знает, что когда в игре соревнуются спортсмены с рейтингами $$$x$$$ и $$$y$$$, и при этом $$$|x - y| > k$$$, спортсмен с более высоким рейтингом обязательно побеждает. Но если $$$|x - y| \le k$$$, победить может любой из двух спортсменов.

Среди всех $$$n!$$$ способов назначить индексы участникам посчитайте количество таких способов, что Монокарп может точно спрогнозировать результат каждой из $$$n-1$$$ игр. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 10^6$$$; $$$0 \le k \le 10^9$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$).

Выходные данные

Выведите одно целое число — количество способов назначить участникам индексы так, чтобы Монокарп мог точно предсказать результат каждой из $$$n-1$$$ игр.

Примеры
Входные данные
4 3
7 12 17 21
Выходные данные
24
Входные данные
3 7
4 9 28
Выходные данные
4
Входные данные
4 1
1 2 3 4
Выходные данные
0
Входные данные
4 1
1 2 2 4
Выходные данные
12
Входные данные
16 30
8 12 15 27 39 44 49 50 51 53 58 58 59 67 68 100
Выходные данные
527461297
Примечание

В первом примере Монокарп точно знает результат игры между любой парой игроков, поэтому все $$$24$$$ способа назначить индексы игрокам подходят.

Во втором примере подходящие способы назначить индексы — такие: $$$[1, 3, 2]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2$$$] и $$$[3, 2, 1]$$$.