할 일이 없어진 밍구는 복사 붙여넣기 놀이를 하고 있다! 복사 붙여넣기 놀이는 파일을 복사 붙여넣기하면서 생기는 이름을 살펴보는 놀이이다.

파일의 이름은 $0$ 이상 $2^w$ 미만의 정수로 이루어진 길이 $1$ 이상의 수열이다. 한 번의 복사 붙여넣기는 다음 절차로 이루어진다.

• 복사 과정: 폴더에 있는 모든 파일을 선택한다.
• 붙여넣기 과정: 각 선택된 파일 $S$에 대해서 다음을 반복한다. 이때 새로 생성한 파일은 선택되지 않는다.
  • $S$의 뒤에 $0$을 추가한 이름을 가진 파일을 생성한다. 단, 이미 같은 이름을 가진 파일이 있다면 생성하지 않는다.
  • $0 \le i \lt w$인 모든 $i$에 대해, $S$의 마지막 원소에 $2^i$를 XOR한 이름을 가진 파일을 생성한다. 단, 이미 같은 이름을 가진 파일이 있다면 생성하지 않는다.
• 붙여넣기 과정이 끝난 후, 모든 선택된 파일을 선택 해제한다.

예를 들어, $w=2$이고, 폴더에 파일이 $[0]$ 하나만 있을 때 복사 붙여넣기를 반복하면 폴더의 내용물은 다음과 같이 변한다.

• 초기 상황: $[0]$
• 1회: $[0]$, $[0, 0]$, $[1]$, $[2]$
• 2회: $[0]$, $[0, 0]$, $[0, 0, 0]$, $[0, 1]$, $[0, 2]$, $[1]$, $[1, 0]$, $[2]$, $[2, 0]$, $[3]$

복사 붙여넣기 고수 밍구는 여러분에게 다음과 같은 문제를 주었다. 폴더에 파일이 $[0]$ 하나만 있는 상황에서 K번 복사 붙여넣기를 했을 때, 밍구가 주는 파일의 이름 A가 사전 순으로 몇 번째에 위치하는지 구하는 것이다!

밍구를 위해 A가 사전 순으로 위치하는 순서를 $998\,244\,353$으로 나눈 나머지를 구해주자!

Input

첫째 줄에 정수 w, K가 공백으로 구분되어 주어진다. ($1 \le w \le 60$; $1 \le K \le 100\,000$)

둘째 줄에 찾고자 하는 파일의 이름 A의 길이 N이 주어진다. ($1 \le N \le 100\,000$)

셋째 줄에 A의 $i$번째 원소 A_i들이 공백으로 구분되어 주어진다. ($1 \le i \le N$)

복사 붙여넣기를 K번 했을 때 A의 이름을 가지는 파일이 존재하는 경우만 입력으로 주어진다.

Output

사전순으로 가장 앞서는 파일의 순서를 $1$이라고 할 때, A가 사전순으로 위치하는 순서를 $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 = [a_1, a_2, \cdots, a_n]$이 수열 $b = [b_1, b_2, \cdots, b_m]$보다 사전순으로 앞선다는 것은 다음을 모두 만족시키는 양의 정수 $i$가 존재한다는 뜻이다.

• $i$보다 작은 모든 양의 정수 $j$에 대해, $a_j$와 $b_j$ 모두 존재하면서 $a_j = b_j$
• $b_i$가 존재함
• $a_i$가 존재하지 않거나 $a_i < b_i$