Levyllä #1 on tallennettuna binäärijono $s_1$, jonka pituus on $m$.
Tämän jälkeen tehdään $n - 1$ operaatiota. $i$:nnessä operaatiossa valitaan levy $1 \le p_{i+1} \le i$, ja kyseisellä levyllä oleva merkkijono $s_{p_{i+1}}$ kopioidaan levylle $i + 1$, jolloin syntyy $s_{i+1}$. Kopiointiprosessin aikana kuitenkin enintään $k$ bittiä voi kääntyä (eli virheitä tapahtuu korkeintaan $k$ kohdassa).
Sinulle annetaan kaikki lopulliset $n$ binäärijonoa $s_1, s_2, \dots, s_n$, joista jokaisen pituus on $m$. Tehtäväsi on määrittää, kuinka moni mahdollinen jono $p_2, p_3, \dots, p_n$ voisi johtaa tähän lopputilanteeseen.
Koska vastaus voi olla suuri, sinun tarvitsee vain selvittää vastaus modulo $998244353$.
Syöte
Syötteen ensimmäinen rivi sisältää kolme kokonaislukua $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), jotka on kuvattu tehtävänannossa. On taattu, että $m$ on $4$:n monikerta.
Jokainen seuraavista $n$ rivistä sisältää heksadesimaalimerkkijonon $s'_i$, jonka pituus on $m/4$. Jokainen merkkijonon $s'_i$ merkki on jokin merkeistä 0–9 tai A–F, missä $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Jokainen heksadesimaaliesityksen $s'_i$ numero vastaa neljää peräkkäistä bittiä binäärijonossa $s_i$. Tarkemmin sanottuna jokaiselle numerolle $s'_{i,j}$ voidaan todistaa, että on olemassa yksikäsitteinen nelikko $(a, b, c, d)$, joka toteuttaa ehdot $s'_{i,j} = 8a + 4b + 2c + d$ ja $a, b, c, d \in \{0, 1\}$. Binäärijonon $s_i$ bitit toteuttavat yhtälön $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Tuloste
Tulosta kokonaisluku — kelvollisten jonojen $(p_2, p_3, \dots, p_n)$ lukumäärä modulo $998244353$.
Esimerkki
5 8 2
95
05
BD
9C
BD
6