Рассмотрим турнир, в котором участвуют \(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-1\) игр.
Примечание
В первом примере Монокарп точно знает результат игры между любой парой игроков, поэтому все \(24\) способа назначить индексы игрокам подходят.
Во втором примере подходящие способы назначить индексы — такие: \([1, 3, 2]\), \([2, 3, 1]\), \([3, 1, 2\)] и \([3, 2, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
7 12 17 21
|
24
|
|
2
|
3 7
4 9 28
|
4
|
|
3
|
4 1
1 2 3 4
|
0
|
|
4
|
4 1
1 2 2 4
|
12
|
|
5
|
16 30
8 12 15 27 39 44 49 50 51 53 58 58 59 67 68 100
|
527461297
|