Contexto del problema

A menudo recuerdo el pasado...

Hace tres años, la pequeña Tangyuan era una adorable estudiante de primer año de secundaria, y en aquel entonces era compañera de clase de Yuting-jiang...

Descripción

Volviendo al tema, la pequeña Tangyuan resolvió el siguiente problema en un club de matemáticas de primer año:

Demuestre que para cualquier secuencia de longitud $4$ que contenga solo $\pm1$, $a_0, a_1, a_2, a_3$, se cumple que $4 \mid a_0a_1+a_1a_2+a_2a_3+a_3a_0$.

La adorable Tangyuan resolvió este problema al instante, lo que la hizo sentir muy feliz. Tres años después, habiendo desarrollado un $\overset{\text{counting}}{\text{mal hábito}}$, quiere mejorar este problema 🥰

Para una secuencia de longitud $n$ que contiene solo $\pm1$, $a_0 \dots a_{n-1}$, definimos su función de lluvia: $$ S(a, m) = \displaystyle \sum_{k = 0}^{n - 1} \prod_{l = 0}^{m - 1} a_{(k + l) \bmod n} $$ Dados $n, m, k$, calcule cuántas de las $2^n$ secuencias $a$ diferentes tienen un valor de función de lluvia $S(a, m) = k$. Imprima el resultado módulo $998,244,353$.

Entrada

Este problema contiene múltiples casos de prueba.

La primera línea contiene un entero positivo $T$ que indica el número de casos de prueba.

Las siguientes $T$ líneas contienen tres enteros cada una, que representan $n, m, k$ respectivamente.

Salida

Se deben imprimir $T$ líneas, cada una con un entero que representa la respuesta para un caso de prueba.

Ejemplos

Entrada 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

Salida 1

12
256
108
10000
661235724
741150826
500003636
222931421
404094315

Nota 1

Para el primer caso de la primera muestra, las secuencias que no cumplen la condición son $a=[1,1,1,1]$, $a=[-1,-1,-1,-1]$, $a=[1,-1,1,-1]$ y $a=[-1,1,-1,1]$, por lo que la respuesta es $2^4-4=12$.

Para el segundo caso de la primera muestra, las secuencias que cumplen la condición son aquellas en las que $a$ tiene un número impar de $-1$, por lo que la respuesta es $2^8=256$.

Entrada 2

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

Salida 2

176
1728
26160
368000
5413856
80212608

Entrada 3

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

Salida 3

0
0
0
0

Subtareas

Este problema utiliza pruebas agrupadas.

Para todos los datos, se garantiza que $2 \leq m \leq n \leq 5\times 10^6$, $0 \leq \lvert k\rvert \leq n$, $1 \leq T \leq 10$ y $\sum n \leq 5\times 10^6$.