복사 붙여넣기

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

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

• 복사 과정: 폴더에 있는 모든 파일을 선택한다.
• 붙여넣기 과정: 선택된 각 파일 $S$에 대해 다음을 반복한다. 이때 새로 만든 파일은 선택되지 않는다.
  • $S$의 뒤에 0을 추가한 이름을 가진 파일을 만든다. 단, 이미 같은 이름을 가진 파일이 있다면 만들지 않는다.
  • $0 \le i < 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으로 나눈 나머지를 구해 주자.

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

둘째 줄에 파일 이름 $A$의 길이 $N$이 주어진다. ($1 \le N \le 100000$)

셋째 줄에 $A$의 $i$번째 원소 $A_i$가 공백으로 구분되어 주어진다. ($1 \le i \le N$; $0 \le A_i < 2^w$)

복사 붙여넣기를 $K$번 한 후에 이름이 $A$인 파일이 존재하는 경우에만 입력이 주어진다.

사전 순으로 가장 앞서는 파일의 순서를 1이라고 할 때, $A$가 사전 순으로 위치하는 순서를 998 244 353으로 나눈 나머지를 출력한다.

수열 $a = [a_1, a_2, \ldots, a_n]$이 수열 $b = [b_1, b_2, \ldots, b_m]$보다 사전순으로 앞선다는 것은, 다음을 모두 만족하는 양의 정수 $i$가 존재한다는 뜻이다.

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