Na dysku #1 zapisany jest ciąg binarny $s_1$ o długości $m$.
Następnie wykonywanych jest $n - 1$ operacji. W $i$-tej operacji wybierany jest dysk $1 \le p_{i+1} \le i$, a ciąg $s_{p_{i+1}}$ znajdujący się na tym dysku jest kopiowany na dysk $i + 1$, tworząc $s_{i+1}$. Jednak podczas procesu kopiowania co najwyżej $k$ bitów może zostać odwróconych (tzn. błędy występują na co najwyżej $k$ pozycjach).
Dane są wszystkie końcowe $n$ ciągów binarnych $s_1, s_2, \dots, s_n$, każdy o długości $m$. Twoim zadaniem jest określenie, ile możliwych ciągów $p_2, p_3, \dots, p_n$ mogło doprowadzić do tej końcowej konfiguracji.
Ponieważ odpowiedź może być duża, wystarczy znaleźć odpowiedź modulo $998244353$.
Wejście
Pierwszy wiersz wejścia zawiera trzy liczby całkowite $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), opisane w treści zadania. Gwarantowane jest, że $m$ jest wielokrotnością $4$.
Każdy z kolejnych $n$ wierszy zawiera ciąg szesnastkowy $s'_i$ o długości $m/4$. Każdy znak ciągu $s'_i$ to jeden ze znaków 0–9 lub A–F, gdzie $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Każda cyfra w zapisie szesnastkowym $s'_i$ odpowiada czterem kolejnym bitom w ciągu binarnym $s_i$. Dokładniej, dla każdej cyfry $s'_{i,j}$ można udowodnić, że istnieje dokładnie jedna czwórka $(a, b, c, d)$ spełniająca $s'_{i,j} = 8a + 4b + 2c + d$ oraz $a, b, c, d \in \{0, 1\}$. Bity w ciągu binarnym $s_i$ spełniają $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Wyjście
Wypisz jedną liczbę całkowitą — liczbę poprawnych ciągów $(p_2, p_3, \dots, p_n)$ modulo $998244353$.
Przykład
5 8 2
95
05
BD
9C
BD
6