Minggu, having nothing to do, is playing a copy-paste game! The copy-paste game is a game where one examines the names that arise while copying and pasting files.

A file name is a sequence of length at least $1$ consisting of integers between $0$ and $2^w - 1$, inclusive. One copy-paste operation proceeds as follows:

• Copy step: Select all files in the folder.
• Paste step: For each selected file $S$, repeat the following (newly created files are not selected):
  • Create a file whose name is $S$ with a $0$ appended at the end. However, if a file with the same name already exists, do not create it.
  • For every $i$ such that $0 \le i < w$, create a file whose name is $S$ with its last element XORed by $2^i$. However, if a file with the same name already exists, do not create it.
• After the paste step finishes, deselect all selected files.

For example, when $w = 2$ and the folder initially contains only the file $[0]$, the contents of the folder after repeatedly applying the copy-paste operation change as follows.

• Initial state: $[0]$
• After 1 operation: $[0]$, $[0, 0]$, $[1]$, $[2]$
• After 2 operations: $[0]$, $[0, 0]$, $[0, 0, 0]$, $[0, 1]$, $[0, 2]$, $[1]$, $[1, 0]$, $[2]$, $[2, 0]$, $[3]$

Minggu, a master of copy-paste, gives you the following problem. Starting with only the file $[0]$ in the folder, after performing K copy-paste operations, find the lexicographic rank of the file whose name is A given by Minggu!

For Minggu, compute the rank of A in lexicographic order modulo $998\,244\,353$!

Input

The first line contains two integers w and K, separated by a space. ($1 \le w \le 60$; $1 \le K \le 100\,000$)

The second line contains the length N of the file name A to find. ($1 \le N \le 100\,000$)

The third line contains the elements A_i of A separated by spaces, for $1 \le i \le N$.

It is guaranteed that a file with name A exists after performing K copy-paste operations.

Output

Assuming the lexicographically smallest file is at position $1$, output the remainder when the lexicographic rank of A is divided by $998\,244\,353$.

Examples

Input 1

2 2
3
0 0 0

Output 1

3

Input 2

2 2
1
3

Output 2

10

Input 3

60 2024
4
998244353 1000000007 3141592653 2718281828

Output 3

62474228

Note

A sequence $a = [a_1, a_2, \cdots, a_n]$ is said to be lexicographically smaller than a sequence $b = [b_1, b_2, \cdots, b_m]$ if there exists a positive integer $i$ satisfying all of the following:

• For every positive integer $j$ less than $i$, both $a_j$ and $b_j$ exist and $a_j = b_j$,
• $b_i$ exists,
• $a_i$ does not exist or $a_i < b_i$.