There is a binary string $s_1$ of length $m$ stored on disk #1.
Then, there are $n - 1$ operations. In the $i$-th operation, a disk $1 \le p_{i+1} \le i$ is chosen, and the string $s_{p_{i+1}}$ on that disk is copied to disk $i + 1$, producing $s_{i+1}$. However, during the copying process, up to $k$ bits may be flipped (i.e., errors occur in at most $k$ positions).
You are given all the final $n$ binary strings $s_1, s_2, \dots, s_n$, each of length $m$. Your task is to determine how many possible sequences $p_2, p_3, \dots, p_n$ could result in this final configuration.
Since the answer can be large, you only need to find the answer modulo $998244353$.
Input
The first line of the input contains three integers $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), described in the statement. It is guaranteed that $m$ is a multiple of $4$.
Each of the next $n$ lines contains a hexadecimal string $s'_i$ of length $m/4$. Each character of $s'_i$ is one of 0–9 or A–F, where $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Each bit in the hexadecimal representation $s'_i$ corresponds to four consecutive bits in the binary string $s_i$. Specifically, for each bit $s'_{i,j}$, it can be proved that there exists a unique tuple $(a, b, c, d)$ satisfying $s'_{i,j} = 8a + 4b + 2c + d$ and $a, b, c, d \in \{0, 1\}$. Bits in the binary string $s_i$ satisfy $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Output
Print an integer — the number of valid sequences $(p_2, p_3, \dots, p_n)$ modulo $998244353$.
Example
5 8 2
95
05
BD
9C
BD
6