Có một xâu nhị phân $s_1$ độ dài $m$ được lưu trên đĩa #1.
Sau đó, có $n - 1$ thao tác. Trong thao tác thứ $i$, một đĩa $1 \le p_{i+1} \le i$ được chọn, và xâu $s_{p_{i+1}}$ trên đĩa đó được sao chép sang đĩa $i + 1$, tạo ra $s_{i+1}$. Tuy nhiên, trong quá trình sao chép, tối đa $k$ bit có thể bị lật (tức là lỗi xảy ra ở nhiều nhất $k$ vị trí).
Bạn được cho tất cả $n$ xâu nhị phân cuối cùng $s_1, s_2, \dots, s_n$, mỗi xâu có độ dài $m$. Nhiệm vụ của bạn là xác định có bao nhiêu dãy $p_2, p_3, \dots, p_n$ có thể dẫn đến cấu hình cuối cùng này.
Vì đáp án có thể rất lớn, bạn chỉ cần tìm đáp án theo modulo $998244353$.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), được mô tả trong đề bài. Dữ liệu đảm bảo rằng $m$ là bội số của $4$.
Mỗi dòng trong $n$ dòng tiếp theo chứa một xâu thập lục phân $s'_i$ có độ dài $m/4$. Mỗi ký tự của $s'_i$ là một trong 0–9 hoặc A–F, trong đó $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Mỗi chữ số trong biểu diễn thập lục phân $s'_i$ tương ứng với bốn bit liên tiếp trong xâu nhị phân $s_i$. Cụ thể, với mỗi chữ số $s'_{i,j}$, có thể chứng minh rằng tồn tại duy nhất một bộ bốn $(a, b, c, d)$ thỏa mãn $s'_{i,j} = 8a + 4b + 2c + d$ và $a, b, c, d \in \{0, 1\}$. Các bit trong xâu nhị phân $s_i$ thỏa mãn $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Kết quả
In ra một số nguyên — số lượng dãy hợp lệ $(p_2, p_3, \dots, p_n)$ theo modulo $998244353$.
Ví dụ
5 8 2
95
05
BD
9C
BD
6