XOR 합

$k$비트 정수 $n$개로 이루어진 배열 $a_1, a_2, \ldots, a_n$이 주어진다.

$\sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i \oplus a_j)^x$를 계산한다.

$a \oplus b$는 $a$와 $b$의 비트 단위 배타적 논리합(XOR)이다.

답이 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫 줄에 세 정수 $n$, $k$, $x$가 주어진다 ($1 \leq n, k, n \cdot k \leq 300\,000$, $1 \leq x \leq 3$). 각각 배열의 길이, 각 수의 비트 수, XOR 결과에 씌우는 거듭제곱 지수이다.

다음 $n$개의 줄에는 '0'과 '1'로만 이루어진 문자열 $s_0, s_1, \ldots, s_{k-1}$이 한 줄에 하나씩 주어진다. $i$번째 문자열은 $a_i = \sum_{i=0}^{k-1} s_i \cdot 2^i$를 나타낸다.

모든 쌍에 대해 XOR 결과의 $x$제곱을 구하고, 그 합을 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.

첫 번째 샘플에서 배열은 $[5, 4, 4]$이고, 답은 $(5 \oplus 4) + (5 \oplus 4) + (4 \oplus 4) = 1 + 1 + 0 = 2$이다.

두 번째 샘플에서 배열은 $[61, 38]$이고, 답은 $(61 \oplus 38)^3 = 27^3 = 19683$이다.