21879번 - XOR sum 서브태스크다국어

You have an array of $n$ $k$-bit numbers $a_1, a_2, \ldots, a_n$.

You need to calculate $\sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i \oplus a_j)^x$.

Operation $a \oplus b$ is bitwise exclusive OR of two numbers $a$ and $b$.

Since the answer can be very large, output it modulo $998\,244\,353$.

The first line of the input contains three integers $n, k, x$ ($1 \leq n, k, n \cdot k \leq 300\,000$, $1 \leq x \leq 3$) --- length of an array, number of bits in each number and the power of exclusive OR operations results in the sum.

Next $n$ lines contain array elements.

The $i$-th of them contains string $s_0, s_1, \ldots, s_{k-1}$, consisting of '0' and '1'.

Then $a_i = $ $\sum_{i=0}^{k-1} s_i \cdot 2^i$.

Print one number --- the remainder of division of the sum of $x$-th powers of exclusive OR results of all pairs of numbers in the array by $998\,244\,353$.

In the first sample array contains integers $[5, 4, 4]$, and the answer is $(5 \oplus 4) + (5 \oplus 4) + (4 \oplus 4) = 1 + 1 + 0 = 2$.

In the second sample array contains integers  $[61, 38]$, and the answer is $(61 \oplus 38)^3 = 27^3 = 19683$.