Problem Description

Given positive integers \( N, M, K \) and a sequence of non-negative integers \( A = (A_1, A_2, \ldots, A_N) \).

For a non-empty sequence of non-negative integers \( B = (B_1, B_2, \ldots, B_{|B|}) \), the score is defined as follows:

• If the length of \( B \) is a multiple of \( M \), then \( (B_1 \oplus B_2 \oplus \dots \oplus B_{|B|})^K \)
• Otherwise, \( 0 \)

Here, \( \oplus \) denotes the bitwise XOR operation.

The bitwise XOR of non-negative integers \( A \) and \( B \), denoted \( A \oplus B \), is defined as follows:
- In the binary representation of \( A \oplus B \), the digit in the \( 2^k \) (where \( k \geq 0 \)) place is \( 1 \) if exactly one of the digits in the \( 2^k \) place in the binary representations of \( A \) and \( B \) is \( 1 \), otherwise it is \( 0 \).

For example, \( 3 \oplus 5 = 6 \) (in binary: \( 011 \oplus 101 = 110 \)).

Generally, the XOR of \( k \) integers \( p_1, \dots, p_k \) is defined as \( (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) \), and it can be proven that this is independent of the order of \( p_1, \dots, p_k \).

Find the sum of the scores for each of the \( 2^N - 1 \) non-empty subsequences of \( A \), modulo \( 998244353 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( M \) \( K \) \( A_1 \) \( A_2 \) \( \ldots \) \( A_N \)

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 2 2
1 2 3

Sample Output #1

14

Sample Input #2

10 5 3
100 100 100 100 100 100 100 100 100 100

Sample Output #2

252000000

Sample Input #3

16 4 100
7053 3876 3178 8422 7802 5998 2334 6757 6889 6637 7365 9495 7848 9026 7312 6558

Sample Output #3

432440016

Notes/Hints

Constraints

• \( 1 \leq N, K \leq 2 \times 10^5 \)
• \( 1 \leq M \leq 100 \)
• \( 0 \leq A_i < 2^{20} \)
• All inputs are integers

Sample Explanation 1

The scores for each of the \( 2^3 - 1 = 7 \) non-empty subsequences of \( A \) are as follows:
- \( (1) \): \( 0 \)
- \( (2) \): \( 0 \)
- \( (3) \): \( 0 \)
- \( (1, 2) \): \( (1 \oplus 2)^2 = 9 \)
- \( (1, 3) \): \( (1 \oplus 3)^2 = 4 \)
- \( (2, 3) \): \( (2 \oplus 3)^2 = 1 \)
- \( (1, 2, 3) \): \( 0 \)

Thus, the sum of the scores is \( 0 + 0 + 0 + 9 + 4 + 1 + 0 = 14 \).

见题面 Input 部分

见题面 Output 部分