明古閒得發慌，正在玩複製貼上遊戲！複製貼上遊戲是一種觀察檔案在複製貼上過程中產生的名稱的遊戲。
檔案的名稱是一個長度至少為 $1$ 的數列，由 $0$ 以上且小於 $2^w$ 的整數組成。一次複製貼上操作包含以下步驟：
- 複製過程：選取資料夾中的所有檔案。
- 貼上過程：對每個被選取的檔案 $S$ 重複以下步驟。注意，新建立的檔案不會被選取。
- 建立一個名稱為在 $S$ 的末尾加上 $0$ 的檔案。但如果已有相同名稱的檔案，則不建立。
- 對所有 $0 \le i \lt w$ 的 $i$，建立一個名稱為將 $S$ 的最後一個元素 XOR 上 $2^i$ 的檔案。但如果已有相同名稱的檔案，則不建立。
- 貼上過程結束後，取消選取所有被選取的檔案。
舉例來說，當 $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$ 滿足以下所有條件，則稱 $a$ 在字典序中比 $b$ 前面：
- 對所有小於 $i$ 的正整數 $j$，$a_j$ 和 $b_j$ 都存在且 $a_j = b_j$。
- $b_i$ 存在。
- $a_i$ 不存在，或者 $a_i < b_i$。