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.
| $\text{Subtask}$ | Puntos | $T \leq$ | $\sum n \leq$ | $m \leq$ |
|---|---|---|---|---|
| $1$ | $5$ | $1$ | $20$ | / |
| $2$ | $10$ | $5$ | $10^5$ | $2$ |
| $3$ | $10$ | $5$ | $10^5$ | $4$ |
| $4$ | $15$ | / | $7\times10^3$ | / |
| $5$ | $20$ | / | $10^5$ | / |
| $6$ | $40$ | / | / | / |
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$.