Minggu không có việc gì làm nên đang chơi trò sao chép và dán! Trò chơi sao chép và dán là xem xét tên được sinh ra khi sao chép và dán các tệp.

Tên của tệp là một dãy số có độ dài ít nhất 1, gồm các số nguyên không âm nhỏ hơn $2^w$. Một lần sao chép và dán được thực hiện theo quy trình sau:

• Quá trình sao chép: Chọn tất cả các tệp trong thư mục.
• Quá trình dán: Đối với mỗi tệp được chọn $S$, lặp lại các bước sau. Lưu ý rằng các tệp mới tạo không được chọn.
  • Tạo một tệp có tên là $S$ với số $0$ được thêm vào cuối. Tuy nhiên, nếu đã tồn tại một tệp có cùng tên thì không tạo.
  • Với mọi $i$ thỏa mãn $0 \le i < w$, tạo một tệp có tên là $S$ với phần tử cuối cùng được XOR với $2^i$. Tuy nhiên, nếu đã tồn tại một tệp có cùng tên thì không tạo.
• Sau khi quá trình dán kết thúc, bỏ chọn tất cả các tệp đã chọn.

Ví dụ, với $w=2$, khi thư mục chỉ có một tệp $[0]$, nếu lặp lại thao tác sao chép và dán, nội dung thư mục thay đổi như sau:

• Ban đầu: $[0]$
• Lần 1: $[0]$, $[0, 0]$, $[1]$, $[2]$
• Lần 2: $[0]$, $[0, 0]$, $[0, 0, 0]$, $[0, 1]$, $[0, 2]$, $[1]$, $[1, 0]$, $[2]$, $[2, 0]$, $[3]$

Cao thủ sao chép và dán Minggu đã đưa ra cho các bạn bài toán sau đây. Trong tình huống thư mục chỉ có một tệp $[0]$, sau khi thực hiện sao chép và dán K lần, hãy tìm thứ tự từ điển của tên tệp A do Minggu đưa ra!

Hãy giúp Minggu tìm số dư khi chia thứ tự từ điển của A cho $998\,244\,353$!

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên w, K, cách nhau bởi dấu cách. ($1 \le w \le 60$; $1 \le K \le 100\,000$)

Dòng thứ hai chứa độ dài N của tên tệp A cần tìm. ($1 \le N \le 100\,000$)

Dòng thứ ba chứa các phần tử A_i của A, cách nhau bởi dấu cách. ($1 \le i \le N$)

Đầu vào đảm bảo rằng tệp có tên A tồn tại sau khi thực hiện sao chép và dán K lần.

Dữ liệu ra

Gọi thứ tự của tệp đứng đầu theo thứ tự từ điển là $1$. In ra số dư khi chia thứ tự từ điển của A cho $998\,244\,353$.

Ví dụ

Đầu vào 1

2 2
3
0 0 0

Đầu ra 1

3

Đầu vào 2

2 2
1
3

Đầu ra 2

10

Đầu vào 3

60 2024
4
998244353 1000000007 3141592653 2718281828

Đầu ra 3

62474228

Ghi chú

Dãy số $a = [a_1, a_2, \cdots, a_n]$ được gọi là đứng trước dãy số $b = [b_1, b_2, \cdots, b_m]$ theo thứ tự từ điển nếu tồn tại số nguyên dương $i$ thỏa mãn tất cả các điều sau:

• Với mọi số nguyên dương $j$ nhỏ hơn $i$, cả $a_j$ và $b_j$ đều tồn tại và $a_j = b_j$.
• $b_i$ tồn tại.
• $a_i$ không tồn tại hoặc $a_i < b_i$.