e-olymp
Competitions

2018 Innopolice First Stage, December 1

XOR sum

You have an array of n k-bit numbers a1, a2, ..., an. You need to calculate

prb8647.gif

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

prb8647_1.gif

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