На диску #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