Hay una cadena binaria $s_1$ de longitud $m$ almacenada en el disco #1.
Luego, se realizan $n - 1$ operaciones. En la $i$-ésima operación, se elige un disco $1 \le p_{i+1} \le i$, y la cadena $s_{p_{i+1}}$ de ese disco se copia al disco $i + 1$, produciendo $s_{i+1}$. Sin embargo, durante el proceso de copia, hasta $k$ bits pueden invertirse (es decir, ocurren errores en a lo sumo $k$ posiciones).
Se te dan todas las $n$ cadenas binarias finales $s_1, s_2, \dots, s_n$, cada una de longitud $m$. Tu tarea es determinar cuántas sucesiones posibles $p_2, p_3, \dots, p_n$ podrían dar lugar a esta configuración final.
Como la respuesta puede ser grande, solo necesitas hallar la respuesta módulo $998244353$.
Entrada
La primera línea de la entrada contiene tres enteros $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), descritos en el enunciado. Se garantiza que $m$ es múltiplo de $4$.
Cada una de las siguientes $n$ líneas contiene una cadena hexadecimal $s'_i$ de longitud $m/4$. Cada carácter de $s'_i$ es uno de 0–9 o A–F, donde $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Cada dígito en la representación hexadecimal $s'_i$ corresponde a cuatro bits consecutivos en la cadena binaria $s_i$. Específicamente, para cada dígito $s'_{i,j}$, se puede demostrar que existe una única tupla $(a, b, c, d)$ que satisface $s'_{i,j} = 8a + 4b + 2c + d$ y $a, b, c, d \in \{0, 1\}$. Los bits en la cadena binaria $s_i$ satisfacen $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Salida
Imprime un entero — el número de sucesiones válidas $(p_2, p_3, \dots, p_n)$ módulo $998244353$.
Ejemplo
5 8 2
95
05
BD
9C
BD
6