Une chaîne binaire $s_1$ de longueur $m$ est stockée sur le disque #1.
Ensuite, il y a $n - 1$ opérations. Lors de la $i$-ème opération, un disque $1 \le p_{i+1} \le i$ est choisi, et la chaîne $s_{p_{i+1}}$ présente sur ce disque est copiée sur le disque $i + 1$, produisant $s_{i+1}$. Cependant, pendant le processus de copie, jusqu'à $k$ bits peuvent être inversés (c'est-à-dire que des erreurs se produisent dans au plus $k$ positions).
On vous donne l'ensemble des $n$ chaînes binaires finales $s_1, s_2, \dots, s_n$, chacune de longueur $m$. Votre tâche consiste à déterminer combien de suites possibles $p_2, p_3, \dots, p_n$ pourraient aboutir à cette configuration finale.
Comme la réponse peut être grande, vous devez seulement trouver la réponse modulo $998244353$.
Entrée
La première ligne de l'entrée contient trois entiers $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), décrits dans l'énoncé. Il est garanti que $m$ est un multiple de $4$.
Chacune des $n$ lignes suivantes contient une chaîne hexadécimale $s'_i$ de longueur $m/4$. Chaque caractère de $s'_i$ est l'un des caractères 0–9 ou A–F, où $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Chaque chiffre de la représentation hexadécimale $s'_i$ correspond à quatre bits consécutifs dans la chaîne binaire $s_i$. Plus précisément, pour chaque chiffre $s'_{i,j}$, on peut prouver qu'il existe un unique quadruplet $(a, b, c, d)$ vérifiant $s'_{i,j} = 8a + 4b + 2c + d$ et $a, b, c, d \in \{0, 1\}$. Les bits de la chaîne binaire $s_i$ vérifient $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Sortie
Affichez un entier — le nombre de suites valides $(p_2, p_3, \dots, p_n)$ modulo $998244353$.
Exemple
5 8 2
95
05
BD
9C
BD
6