На диске #1 хранится двоичная строка $s_1$ длины $m$.
Затем выполняется $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$ строк содержит шестнадцатеричную строку $s'_i$ длины $m/4$. Каждый символ строки $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