磁盘 #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 之一，其中 A = 10, B = 11, ..., 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 取模后的结果。

样例

输入样例 1

5 8 2
95
05
BD
9C
BD

输出样例 1

6