在 $1$ 號磁碟上儲存著一個長度為 $m$ 的二進位字串 $s_1$。
接著進行 $n - 1$ 次操作。在第 $i$ 次操作中,會選擇一個滿足 $1 \le p_{i+1} \le i$ 的磁碟,並將該磁碟上的字串 $s_{p_{i+1}}$ 複製到磁碟 $i + 1$,從而產生 $s_{i+1}$。然而,在複製過程中,最多可能有 $k$ 個位元發生翻轉(即最多在 $k$ 個位置發生錯誤)。
現在給定最終的所有 $n$ 個二進位字串 $s_1, s_2, \dots, s_n$,每個字串的長度皆為 $m$。你的任務是求出有多少種可能的序列 $p_2, p_3, \dots, p_n$ 可以產生這個最終狀態。
由於答案可能很大,你只需要求出答案對 $998244353$ 取模後的結果。
輸入格式
輸入的第一行包含三個整數 $n, m, k$($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$),其含義如題目所述。保證 $m$ 是 $4$ 的倍數。
接下來的 $n$ 行,每行包含一個長度為 $m/4$ 的十六進位字串 $s'_i$。$s'_i$ 的每個字元皆為 0–9 或 A–F 之一,其中 $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$。
十六進位表示 $s'_i$ 中的每一位對應二進位字串 $s_i$ 中的四個連續位元。具體而言,對於每一位 $s'_{i,j}$,可以證明存在唯一的四元組 $(a, b, c, d)$ 滿足 $s'_{i,j} = 8a + 4b + 2c + d$ 且 $a, b, c, d \in \{0, 1\}$。二進位字串 $s_i$ 中的位元滿足 $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$。
輸出格式
輸出一個整數 — 合法序列 $(p_2, p_3, \dots, p_n)$ 的數量對 $998244353$ 取模後的結果。
範例
5 8 2
95
05
BD
9C
BD
6