시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 1 1 100.000%

문제

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$.

서브태스크

번호 배점 제한
1 5

$n \leq 5000, k \leq 30$

2 5

$n \cdot k \leq 5000$

3 5

$k \leq 30$, $a_i = 2^{b_i}$ for some $b_i$

4 10

$k \leq 20$

5 10

$x = 1, n \cdot k \leq 300\,000$

6 15

$x \leq 2, n \cdot k \leq 100\,000$

7 10

$x \leq 2, n \cdot k \leq 300\,000$

8 15

$n \cdot k \leq 100\,000$

9 10

$n \cdot k \leq 200\,000$

10 15

$n \cdot k \leq 300\,000$

예제 입력 1

3 3 1
101
001
001

예제 출력 1

2

예제 입력 2

2 6 3
101111
011001

예제 출력 2

19683

힌트

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$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.