XOR sum
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 (1 ≤ n, k, n * k ≤ 300 000, 1 ≤ x ≤ 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 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.
3 3 1 101 001 001
2
2 6 3 101111 011001
19683