Это сложная версия задачи. Разница между двумя версиями заключается в ограничениях на \(n, m, b_0\) и ограничении по времени. Вы можете делать взломы, только если обе версии решены.
Малышка R уже посчитала множество множеств, и теперь она решила посчитать массивы.
Малышка R считает, что массив \(b_0, \ldots, b_n\), состоящий из целых неотрицательных чисел, является непрерывным тогда и только тогда, когда для каждого \(i\), такого что \(1 \leq i \leq n\), выполняется \(\lvert b_i - b_{i-1} \rvert = 1\). Ей нравится непрерывность, поэтому она хочет генерировать только непрерывные массивы.
Если малышке R даны \(b_0\) и \(a_1, \ldots, a_n\), то она попытается сгенерировать неотрицательный непрерывный массив \(b\), который не имеет сходства с \(a\). Более формально, для всех \(1 \leq i \leq n\), \(a_i \neq b_i\).
Однако у малышки R нет никакого массива \(a\). Вместо этого она дала вам \(n\), \(m\) и \(b_0\). Она хочет посчитать количество различных целочисленных массивов \(a_1, \ldots, a_n\), удовлетворяющих условиям:
- \(1 \leq a_i \leq m\);
- Можно сгенерировать хотя бы один неотрицательный непрерывный массив \(b_0, \ldots, b_n\).
Заметим, что \(b_i \geq 0\), но \(b_i\) может быть произвольно большим.
Поскольку ответ может быть очень большим, выведите ответ по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую целое число: количество различных массивов \(a_1, \ldots, a_n\), удовлетворяющих условиям, по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных, например, когда \(a = [1, 2, 1]\), мы можем задать \(b = [1, 0, 1, 0]\). Когда \(a = [1, 1, 2]\), мы можем задать \(b = [1, 2, 3, 4]\). Всего существует \(6\) допустимых вариантов \(a_1, \ldots, a_n\): можно доказать, что только \(a = [2, 1, 1]\) и \(a = [2, 1, 2]\) делают невозможным построение неотрицательной непрерывного \(b_0, \ldots, b_n\), поэтому ответ равен \(2^3 - 2 = 6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 2 1
5 5 3
13 4 1
100 6 7
100 11 3
1000 424 132
|
6
3120
59982228
943484039
644081522
501350342
|