Sul disco #1 è memorizzata una stringa binaria $s_1$ di lunghezza $m$.
Successivamente, vengono eseguite $n - 1$ operazioni. Nella $i$-esima operazione, viene scelto un disco $1 \le p_{i+1} \le i$, e la stringa $s_{p_{i+1}}$ su quel disco viene copiata sul disco $i + 1$, producendo $s_{i+1}$. Tuttavia, durante il processo di copia, fino a $k$ bit possono essere invertiti (ovvero, si verificano errori in al più $k$ posizioni).
Ti vengono date tutte le $n$ stringhe binarie finali $s_1, s_2, \dots, s_n$, ciascuna di lunghezza $m$. Il tuo compito è determinare quante possibili sequenze $p_2, p_3, \dots, p_n$ potrebbero portare a questa configurazione finale.
Poiché la risposta può essere grande, devi solo trovare la risposta modulo $998244353$.
Input
La prima riga dell'input contiene tre interi $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), descritti nel testo. È garantito che $m$ sia un multiplo di $4$.
Ciascuna delle successive $n$ righe contiene una stringa esadecimale $s'_i$ di lunghezza $m/4$. Ogni carattere di $s'_i$ è uno tra 0–9 oppure A–F, dove $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Ogni cifra nella rappresentazione esadecimale $s'_i$ corrisponde a quattro bit consecutivi nella stringa binaria $s_i$. Nello specifico, per ogni cifra $s'_{i,j}$, si può dimostrare che esiste un'unica tupla $(a, b, c, d)$ che soddisfa $s'_{i,j} = 8a + 4b + 2c + d$ e $a, b, c, d \in \{0, 1\}$. I bit nella stringa binaria $s_i$ soddisfano $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Output
Stampa un intero — il numero di sequenze valide $(p_2, p_3, \dots, p_n)$ modulo $998244353$.
Esempio
5 8 2
95
05
BD
9C
BD
6