Á diski #1 er geymdur tvíundarstrengur $s_1$ af lengd $m$.
Síðan eru framkvæmdar $n - 1$ aðgerðir. Í $i$-tu aðgerðinni er valinn diskur $1 \le p_{i+1} \le i$ og strengurinn $s_{p_{i+1}}$ á þeim diski er afritaður yfir á disk $i + 1$, sem myndar $s_{i+1}$. Hins vegar geta allt að $k$ bitar snúist við í afritunarferlinu (þ.e. villur verða í mesta lagi í $k$ sætum).
Þér eru gefnir allir $n$ loka-tvíundarstrengirnir $s_1, s_2, \dots, s_n$, hver af lengd $m$. Verkefni þitt er að ákvarða hve margar mögulegar runur $p_2, p_3, \dots, p_n$ gætu leitt til þessarar lokaniðurstöðu.
Þar sem svarið getur verið stórt þarftu aðeins að finna svarið modulo $998244353$.
Inntak
Fyrsta lína inntaksins inniheldur þrjár heiltölur $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), eins og lýst er í dæminu. Tryggt er að $m$ sé margfeldi af $4$.
Hver af næstu $n$ línum inniheldur sextándakerfisstreng $s'_i$ af lengd $m/4$. Hvert tákn í $s'_i$ er eitt af 0–9 eða A–F, þar sem $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Hver stafur í sextándakerfisframsetningunni $s'_i$ samsvarar fjórum samliggjandi bitum í tvíundarstrengnum $s_i$. Nánar tiltekið er hægt að sanna fyrir hvern staf $s'_{i,j}$ að til sé ótvírætt fernt $(a, b, c, d)$ sem uppfyllir $s'_{i,j} = 8a + 4b + 2c + d$ og $a, b, c, d \in \{0, 1\}$. Bitarnir í tvíundarstrengnum $s_i$ uppfylla $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Úttak
Prentið heiltölu — fjölda gildra runa $(p_2, p_3, \dots, p_n)$ modulo $998244353$.
Dæmi
5 8 2
95
05
BD
9C
BD
6