Det er lagret en binær streng $s_1$ med lengde $m$ på disk #1.
Deretter utføres det $n - 1$ operasjoner. I den $i$-te operasjonen velges en disk $1 \le p_{i+1} \le i$, og strengen $s_{p_{i+1}}$ på denne disken kopieres til disk $i + 1$, noe som gir $s_{i+1}$. Under kopieringsprosessen kan imidlertid opptil $k$ biter bli snudd (dvs. at det oppstår feil i høyst $k$ posisjoner).
Du får oppgitt alle de $n$ endelige binære strengene $s_1, s_2, \dots, s_n$, hver med lengde $m$. Din oppgave er å bestemme hvor mange mulige følger $p_2, p_3, \dots, p_n$ som kan resultere i denne endelige konfigurasjonen.
Siden svaret kan være stort, trenger du bare å finne svaret modulo $998244353$.
Inndata
Den første linjen i inndataene inneholder tre heltall $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), som beskrevet i oppgaveteksten. Det er garantert at $m$ er et multiplum av $4$.
Hver av de neste $n$ linjene inneholder en heksadesimal streng $s'_i$ med lengde $m/4$. Hvert tegn i $s'_i$ er ett av 0–9 eller A–F, der $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Hvert siffer i den heksadesimale representasjonen $s'_i$ tilsvarer fire påfølgende biter i den binære strengen $s_i$. Mer spesifikt kan det for hvert siffer $s'_{i,j}$ bevises at det finnes en unik tuppel $(a, b, c, d)$ som tilfredsstiller $s'_{i,j} = 8a + 4b + 2c + d$ og $a, b, c, d \in \{0, 1\}$. Bitene i den binære strengen $s_i$ tilfredsstiller $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Utdata
Skriv ut et heltall — antallet gyldige følger $(p_2, p_3, \dots, p_n)$ modulo $998244353$.
Eksempel
5 8 2
95
05
BD
9C
BD
6