Terdapat sebuah string biner $s_1$ dengan panjang $m$ yang disimpan pada diska #1.
Kemudian, terdapat $n - 1$ operasi. Pada operasi ke-$i$, sebuah diska $1 \le p_{i+1} \le i$ dipilih, dan string $s_{p_{i+1}}$ pada diska tersebut disalin ke diska $i + 1$, menghasilkan $s_{i+1}$. Namun, selama proses penyalinan, hingga $k$ bit dapat terbalik (yaitu, kesalahan terjadi pada paling banyak $k$ posisi).
Anda diberikan seluruh $n$ string biner akhir $s_1, s_2, \dots, s_n$, masing-masing dengan panjang $m$. Tugas Anda adalah menentukan berapa banyak barisan $p_2, p_3, \dots, p_n$ yang mungkin yang dapat menghasilkan konfigurasi akhir ini.
Karena jawabannya bisa sangat besar, Anda hanya perlu mencari jawaban modulo $998244353$.
Masukan
Baris pertama masukan berisi tiga bilangan bulat $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$), seperti yang dijelaskan pada deskripsi soal. Dijamin bahwa $m$ adalah kelipatan dari $4$.
Masing-masing dari $n$ baris berikutnya berisi sebuah string heksadesimal $s'_i$ dengan panjang $m/4$. Setiap karakter dari $s'_i$ adalah salah satu dari 0–9 atau A–F, dengan $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
Setiap digit pada representasi heksadesimal $s'_i$ bersesuaian dengan empat bit berurutan pada string biner $s_i$. Secara spesifik, untuk setiap digit $s'_{i,j}$, dapat dibuktikan bahwa terdapat tupel unik $(a, b, c, d)$ yang memenuhi $s'_{i,j} = 8a + 4b + 2c + d$ dan $a, b, c, d \in \{0, 1\}$. Bit-bit pada string biner $s_i$ memenuhi $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$.
Keluaran
Cetak sebuah bilangan bulat — banyaknya barisan valid $(p_2, p_3, \dots, p_n)$ modulo $998244353$.
Contoh
5 8 2
95
05
BD
9C
BD
6