Tło zadania

Często wspominam przeszłość...

Trzy lata temu mała Tangyuan była jeszcze uroczą uczennicą pierwszej klasy gimnazjum, a wtedy chodziła do tej samej klasy co Yuting-jiang...

Treść zadania

Wróćmy do tematu. Na kółku matematycznym w pierwszej klasie mała Tangyuan rozwiązywała następujące zadanie:

Udowodnij, że dla dowolnego ciągu $a_0, a_1, a_2, a_3$ o długości $4$, składającego się wyłącznie z $\pm 1$, zachodzi $4 \mid a_0a_1+a_1a_2+a_2a_3+a_3a_0$.

Urocza Tangyuan rozwiązała to zadanie w mgnieniu oka, co sprawiło jej wielką radość. Trzy lata później, zarażona $\overset{\text{counting}}{\text{złym nawykiem}}$, chce uogólnić ten problem 🥰

Dla ciągu $a_0 \dots a_{n-1}$ o długości $n$, składającego się wyłącznie z $\pm 1$, definiujemy jego funkcję deszczową: $$ S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n} $$ Mając dane $n, m, k$, oblicz, dla ilu spośród $2^n$ różnych ciągów $a$ wartość funkcji deszczowej wynosi $S(a, m) = k$. Wynik podaj modulo $998\,244\,353$.

Wejście

Zadanie zawiera wiele zestawów danych.

Pierwsza linia zawiera liczbę całkowitą $T$ oznaczającą liczbę zestawów danych.

Każda z kolejnych $T$ linii zawiera trzy liczby całkowite $n, m, k$.

Wyjście

Dla każdego zestawu danych wypisz w osobnej linii wynik obliczeń.

Przykład

Przykład 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

Wyjście 1

12
256
108
10000
661235724
741150826
500003636
222931421
404094315

Uwagi 1

Dla pierwszego zestawu danych w pierwszym przykładzie, ciągi niespełniające warunku to $a=[1,1,1,1]$, $a=[-1,-1,-1,-1]$, $a=[1,-1,1,-1]$ oraz $a=[-1,1,-1,1]$, zatem odpowiedź wynosi $2^4-4=12$.

Dla drugiego zestawu danych w pierwszym przykładzie, warunek spełniają tylko te ciągi $a$, w których występuje nieparzysta liczba $-1$, zatem odpowiedź wynosi $2^8=256$.

Przykład 2

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

Wyjście 2

176
1728
26160
368000
5413856
80212608

Przykład 3

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

Wyjście 3

0
0
0
0

Podzadania

Zadanie oceniane jest w systemie testów wiązanych.

Dla wszystkich danych wejściowych gwarantuje się, że $2 \leq m \leq n \leq 5\times 10^6$, $0 \leq \lvert k\rvert \leq n$, $1 \leq T \leq 10$ oraz $\sum n\leq 5\times10^6$.