コピーペースト - Problème

暇になったミングはコピー＆ペースト遊びをしている！コピー＆ペースト遊びとは、ファイルをコピー＆ペーストしながら発生する名前を調べる遊びである。

ファイルの名前は、$0$ 以上 $2^w$ 未満の整数からなる、長さ $1$ 以上の数列である。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$ で割った余りを求めよ！

1行目には整数 w, K が空白区切りで与えられる。($1 \le w \le 60$; $1 \le K \le 100\,000$)

2行目には、探したいファイルの名前 A の長さ N が与えられる。($1 \le N \le 100\,000$)

3行目には、A の $i$ 番目の要素 A_i が空白区切りで与えられる。($1 \le i \le N$)

コピー＆ペーストを K 回行ったときに A という名前のファイルが存在する場合のみが入力として与えられる。

辞書順で最も先頭のファイルの順序を $1$ としたとき、A が辞書順で位置する順序を $998\,244\,353$ で割った余りを出力する。

2 2
3
0 0 0

2 2
1
3

60 2024
4
998244353 1000000007 3141592653 2718281828

62474228

数列 $a = [a_1, a_2, \cdots, a_n]$ が数列 $b = [b_1, b_2, \cdots, b_m]$ より辞書順で先頭であるとは、以下をすべて満たす正の整数 $i$ が存在することである。

QOJ.ac