# 2018 Innopolice First Stage, December 1

# XOR sum

You have an array of **n k**-bit numbers `a`

, _{1}`a`

, ..., _{2}`a`

. You need to calculate_{n}

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 `s`

, _{0}`s`

, ..., _{1}`s`

, consisting of "_{k-1}**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** = `27`

= ^{3}**19683**.

3 3 1 101 001 001

2

2 6 3 101111 011001

19683