Контекст задачи

Я часто вспоминаю прошлое...

Три года назад Сяо Танъюань была милой и очаровательной семиклассницей, и тогда она училась в одном классе с Юйтин-цзян...

Условие задачи

Вернемся к теме: на математическом кружке в седьмом классе Сяо Танъюань решала такую задачу:

Докажите, что для любой последовательности $a_0, a_1, a_2, a_3$ длины $4$, состоящей только из $\pm 1$, выполняется $4 \mid a_0a_1 + a_1a_2 + a_2a_3 + a_3a_0$.

Милая Сяо Танъюань мгновенно решила эту задачу, что принесло ей огромное счастье. Три года спустя, увлекшись $\overset{\text{counting}}{\text{вредными привычками}}$, она захотела усложнить эту задачу 🥰

Для последовательности $a_0 \dots a_{n-1}$ длины $n$, состоящей только из $\pm 1$, определим её «дождевую функцию»: $$ S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n} $$ Даны $n, m, k$. Найдите количество таких последовательностей $a$ из $2^n$ возможных, для которых значение дождевой функции $S(a, m) = k$. Выведите ответ по модулю $998\,244\,353$.

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

В задаче несколько наборов входных данных.

Первая строка содержит целое число $T$ — количество наборов данных.

Далее следуют $T$ строк, каждая из которых содержит три целых числа $n, m, k$.

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

Для каждого набора данных выведите одно целое число — ответ на задачу.

Примеры

Пример 1

9
4 2 0
9 9 -9
9 3 3
20 8 -12
114 5 14
191 9 81
1036 854 104
998244 353 4
2147483 64 7

Вывод 1

12
256
108
10000
661235724
741150826
500003636
222931421
404094315

Примечание к примеру 1

Для первого набора данных первого примера не подходят только $a=[1,1,1,1]$, $a=[-1,-1,-1,-1]$, $a=[1,-1,1,-1]$ и $a=[-1,1,-1,1]$, поэтому ответ $2^4-4=12$.

Для второго набора данных первого примера условию удовлетворяют только те $a$, в которых ровно нечетное количество $-1$, поэтому ответ $2^8=256$.

Пример 2

6
8 4 0
12 4 0
16 4 0
20 4 0
24 4 0
28 4 0

Вывод 2

176
1728
26160
368000
5413856
80212608

Пример 3

4
6 2 0
10 2 0
9 9 7
9 3 6

Вывод 3

0
0
0
0

Подзадачи

В этой задаче используется пакетное тестирование.

Для всех данных гарантируется $2 \leq m \leq n \leq 5\times 10^6$, $0 \leq \lvert k\rvert \leq n$, $1 \leq T \leq 10$, $\sum n \leq 5\times 10^6$.