디스크 #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$개의 위치에서 오류가 발생합니다).
각각 길이가 $m$인 최종 $n$개의 이진 문자열 $s_1, s_2, \dots, s_n$이 모두 주어집니다. 여러분의 목표는 이러한 최종 구성을 만들어낼 수 있는 가능한 수열 $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$인 $16$진수 문자열 $s'_i$가 주어집니다. $s'_i$의 각 문자는 0–9 또는 A–F 중 하나이며, 여기서 $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$입니다.
$16$진수 표현 $s'_i$의 각 자리는 이진 문자열 $s_i$의 연속된 $4$개의 비트에 대응합니다. 구체적으로, 각 자리 $s'_{i,j}$에 대해 $s'_{i,j} = 8a + 4b + 2c + d$와 $a, b, c, d \in \{0, 1\}$을 만족하는 유일한 순서쌍 $(a, b, c, d)$가 존재함을 증명할 수 있습니다. 이진 문자열 $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