Copy and Paste

Mingu, who has nothing left to do, is playing a copy and paste game. The game is about looking at the file names that appear as files are copied and pasted.

A file name is a sequence of length at least 1 whose elements are integers from 0 up to but not including $2^w$. One copy and paste round consists of the following steps.

• Copy step: select every file in the folder.
• Paste step: for each selected file $S$, repeat the following. Files created during this step are not selected.
  • Create a file named $S$ with 0 appended to the end. If a file with the same name already exists, do not create it.
  • For every $i$ with $0 \le i < w$, create a file whose name is the last element of $S$ XORed with $2^i$. If a file with the same name already exists, do not create it.
• After the paste step ends, deselect all selected files.

For example, with $w = 2$ and a folder holding only [0], repeating copy and paste changes the folder contents as follows.

• Start: [0]
• After 1 round: [0], [0, 0], [1], [2]
• After 2 rounds: [0], [0, 0], [0, 0, 0], [0, 1], [0, 2], [1], [1, 0], [2], [2, 0], [3]

Mingu, an expert at copy and paste, gave you the following problem. Starting from a folder that holds only [0], find the position in dictionary order of the file name $A$ that Mingu gives after $K$ rounds of copy and paste.

Find the answer modulo 998 244 353 for Mingu.

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

The second line contains the length $N$ of the file name $A$. ($1 \le N \le 100000$)

The third line contains the elements $A_1, A_2, \ldots, A_N$ of $A$, separated by spaces. ($1 \le i \le N$; $0 \le A_i < 2^w$)

The input is given only when a file named $A$ exists after $K$ rounds of copy and paste.

Let the smallest file name in dictionary order have position 1. Print the position of $A$ in dictionary order, modulo 998 244 353.

A sequence $a = [a_1, a_2, \ldots, a_n]$ comes before a sequence $b = [b_1, b_2, \ldots, b_m]$ in dictionary order when there is a positive integer $i$ that satisfies 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$.