Det finns en binär sträng $s_1$ av längd $m$ lagrad på disk #1.
Därefter utförs $n - 1$ operationer. I den $i$-te operationen väljs en disk $1 \le p_{i+1} \le i$, och strängen $s_{p_{i+1}}$ på den disken kopieras till disk $i + 1$, vilket ger $s_{i+1}$. Under kopieringsprocessen kan dock upp till $k$ bitar inverteras (dvs. fel uppstår på högst $k$ positioner).
Du får alla de slutliga $n$ binära strängarna $s_1, s_2, \dots, s_n$, var och en av längd $m$. Din uppgift är att bestämma hur många möjliga följder $p_2, p_3, \dots, p_n$ som skulle kunna resultera i denna slutliga konfiguration.
Eftersom svaret kan vara stort behöver du bara hitta svaret modulo $998244353$.
Indata
Den första raden i indatan innehåller tre heltal $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), som beskrivs i uppgiften. Det garanteras att $m$ är en multipel av $4$.
Var och en av de följande $n$ raderna innehåller en hexadecimal sträng $s'_i$ av längd $m/4$. Varje tecken i $s'_i$ är ett av 0–9 eller A–F, där $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Varje siffra i den hexadecimala representationen $s'_i$ motsvarar fyra på varandra följande bitar i den binära strängen $s_i$. Mer specifikt kan det för varje siffra $s'_{i,j}$ bevisas att det finns en unik tupel $(a, b, c, d)$ som uppfyller $s'_{i,j} = 8a + 4b + 2c + d$ och $a, b, c, d \in \{0, 1\}$. Bitarna i den binära strängen $s_i$ uppfyller $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Utdata
Skriv ut ett heltal — antalet giltiga följder $(p_2, p_3, \dots, p_n)$ modulo $998244353$.
Exempel
5 8 2
95
05
BD
9C
BD
6