Auf Festplatte #1 ist eine Binärzeichenkette $s_1$ der Länge $m$ gespeichert.
Anschließend gibt es $n - 1$ Operationen. In der $i$-ten Operation wird eine Festplatte $1 \le p_{i+1} \le i$ ausgewählt und die Zeichenkette $s_{p_{i+1}}$ auf dieser Festplatte wird auf Festplatte $i + 1$ kopiert, wodurch $s_{i+1}$ entsteht. Während des Kopiervorgangs können jedoch bis zu $k$ Bits invertiert werden (d. h., es treten an höchstens $k$ Positionen Fehler auf).
Dir sind alle endgültigen $n$ Binärzeichenketten $s_1, s_2, \dots, s_n$ gegeben, jede der Länge $m$. Deine Aufgabe ist es zu bestimmen, wie viele mögliche Folgen $p_2, p_3, \dots, p_n$ zu dieser Endkonfiguration führen könnten.
Da die Antwort groß sein kann, musst du nur die Antwort modulo $998244353$ bestimmen.
Eingabe
Die erste Zeile der Eingabe enthält drei ganze Zahlen $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), wie in der Aufgabenstellung beschrieben. Es wird garantiert, dass $m$ ein Vielfaches von $4$ ist.
Jede der nächsten $n$ Zeilen enthält eine hexadezimale Zeichenkette $s'_i$ der Länge $m/4$. Jedes Zeichen von $s'_i$ ist eines aus 0–9 oder A–F, wobei $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$ gilt.
Jede Stelle in der hexadezimalen Darstellung $s'_i$ entspricht vier aufeinanderfolgenden Bits in der Binärzeichenkette $s_i$. Genauer gesagt lässt sich für jede Stelle $s'_{i,j}$ beweisen, dass ein eindeutiges Tupel $(a, b, c, d)$ existiert, das $s'_{i,j} = 8a + 4b + 2c + d$ und $a, b, c, d \in \{0, 1\}$ erfüllt. Die Bits in der Binärzeichenkette $s_i$ erfüllen $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Ausgabe
Gib eine ganze Zahl aus — die Anzahl der gültigen Folgen $(p_2, p_3, \dots, p_n)$ modulo $998244353$.
Beispiel
5 8 2
95
05
BD
9C
BD
6