 Competitions

# XOR sum

You have an array of n k-bit numbers `a1`, `a2`, ..., `an`. You need to calculate Operation a + b is bitwise exclusive OR of two numbers a and b. Since the answer can be very large, output it modulo 998 244 353.

#### Input

The first line of the input contains three integers n, k, x (1n, k, n * k300 000, 1x3) - 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 `s0`, `s1`, ..., `sk-1`, consisting of "0" and "1". Then #### Output

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.

#### Explanation

In the first test case the array contains the numbers [5, 4, 4], and the resulting sum is (5 xor 4) + (5 xor 4) + (4 xor 4) = 1 + 1 + 0 = 2.

In the second test case the array contains the numbers [61, 38], and the resulting sum is (61 xor 38) ^ 3 = `273` = 19683.

Time limit 1 second
Memory limit 128 MiB
Input example #1
```3 3 1
101
001
001
```
Output example #1
```2
```
Input example #2
```2 6 3
101111
011001
```
Output example #2
```19683
```
Source 2018 Innopolis First Stage, December 1