喺 $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