밍구는 할 일이 없어져서 복사 붙여넣기 놀이를 하고 있다! 복사 붙여넣기 놀이는 파일을 복사하고 붙여넣으면서 생성되는 이름들을 살펴보는 놀이이다.
파일의 이름은 $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$으로 나눈 나머지를 구해주자!
输入格式
첫째 줄에 정수 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의 이름을 가지는 파일이 존재하는 경우만 입력으로 주어진다.
输出格式
사전순으로 가장 앞서는 파일의 순서를 $1$이라고 할 때, A가 사전순으로 위치하는 순서를 $998\,244\,353$으로 나눈 나머지를 출력한다.
样例
样例输入 1
2 2 3 0 0 0
样例输出 1
3
样例输入 2
2 2 1 3
样例输出 2
10
样例输入 3
60 2024 4 998244353 1000000007 3141592653 2718281828
样例输出 3
62474228
说明
수열 $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$