E2. Снова считаем массивы (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Разница между двумя версиями заключается в ограничениях на $$$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$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке указано количество наборов входных данных $$$t\ (1 \leq t \leq 10^4)$$$. Далее следует описание наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$b_0$$$ ($$$1 \leq n \leq 2 \cdot 10^6$$$, $$$1 \leq m \leq 2 \cdot 10^6$$$, $$$0 \leq b_0 \leq 2\cdot 10^6$$$) — длина массива $$$a_1, \ldots, a_n$$$, максимально возможный элемент в $$$a_1, \ldots, a_n$$$, и начальный элемент массива $$$b_0, \ldots, b_n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^7$$$.

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

Для каждого набора входных данных выведите одну строку, содержащую целое число: количество различных массивов $$$a_1, \ldots, a_n$$$, удовлетворяющих условиям, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных, например, когда $$$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$$$.