Contexte du problème

Je me remémore souvent le passé...

Il y a trois ans, la petite Glycogen était encore une adorable élève de première année de collège, et elle était dans la même classe que Yuting-chan...

Énoncé

Revenons au sujet : lors d'un club de mathématiques en première année de collège, la petite Glycogen a résolu le problème suivant :

Démontrer que pour toute séquence $a_0, a_1, a_2, a_3$ de longueur $4$ composée uniquement de $\pm 1$, on a $4 \mid a_0a_1 + a_1a_2 + a_2a_3 + a_3a_0$.

La petite Glycogen a résolu ce problème instantanément à l'époque, ce qui l'a rendue très heureuse. Trois ans plus tard, ayant contracté une $\overset{\text{counting}}{\text{mauvaise habitude}}$, elle souhaite renforcer ce problème 🥰

Pour une séquence $a_0 \dots a_{n-1}$ de longueur $n$ composée uniquement de $\pm 1$, nous définissons sa fonction pluie : $$ S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n} $$ Étant donné $n, m, k$, calculez combien de séquences $a$ parmi les $2^n$ séquences possibles satisfont $S(a, m) = k$. Donnez le résultat modulo $998\,244\,353$.

Entrée

Ce problème comporte plusieurs jeux de données.

La première ligne contient un entier positif $T$ représentant le nombre de jeux de données.

Chaque ligne suivante contient trois entiers $n, m, k$ représentant les paramètres du problème.

Sortie

Le résultat pour chaque jeu de données doit être affiché sur une ligne séparée.

Exemples

Entrée 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

Sortie 1

12
256
108
10000
661235724
741150826
500003636
222931421
404094315

Remarque 1

Pour le premier jeu de données du premier exemple, les seules séquences ne satisfaisant pas la condition sont $a=[1,1,1,1]$, $a=[-1,-1,-1,-1]$, $a=[1,-1,1,-1]$ et $a=[-1,1,-1,1]$, donc la réponse est $2^4-4=12$.

Pour le deuxième jeu de données du premier exemple, les seules séquences satisfaisant la condition sont celles contenant un nombre impair de $-1$, donc la réponse est $2^8=256$.

Entrée 2

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

Sortie 2

176
1728
26160
368000
5413856
80212608

Entrée 3

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

Sortie 3

0
0
0
0

Sous-tâches

Ce problème utilise des tests groupés.

Pour toutes les données, on garantit que $2 \leq m \leq n \leq 5\times 10^6$, $0 \leq \lvert k\rvert \leq n$, $1 \leq T \leq 10$ et $\sum n \leq 5\times 10^6$.