32024번 - 복사 붙여넣기

문제

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

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

• 복사 과정: 폴더에 있는 모든 파일을 선택한다.
• 붙여넣기 과정: 각 선택된 파일 S에 대해서 다음을 반복한다. 이때 새로 생성한 파일은 선택되지 않는다.
  • S의 뒤에 0을 추가한 이름을 가진 파일을 생성한다. 단, 이미 같은 이름을 가진 파일이 있다면 생성하지 않는다.
  • 0 ≤ i < w인 모든 i에 대해, S의 마지막 원소에 2ⁱ를 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 ≤ w ≤ 60; 1 ≤ K ≤ 100 000)

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

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

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

출력

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

제한

노트

수열 a = [a₁, a₂, ⋯, a_n]이 수열 b = [b₁, b₂, ⋯, b_m]보다 사전순으로 앞선다는 것은 다음을 모두 만족시키는 양의 정수 i가 존재한다는 뜻이다.

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