Minggu, który nie ma już nic do roboty, bawi się w kopiuj-wklej! Zabawa w kopiuj-wklej polega na przyglądaniu się nazwom, które powstają podczas kopiowania i wklejania plików.

Nazwa pliku to ciąg liczb całkowitych z zakresu od $0$ do $2^w-1$ (włącznie), o długości co najmniej $1$. Jedna operacja kopiuj-wklej składa się z następujących kroków:

• Kopiowanie: zaznaczane są wszystkie pliki w folderze.
• Wklejanie: dla każdego zaznaczonego pliku $S$ powtarzane jest następujące postępowanie. Nowo utworzone pliki nie są zaznaczane.
  • Tworzony jest plik o nazwie równej $S$ z dodanym na końcu $0$. Jeśli plik o tej samej nazwie już istnieje, nie jest tworzony.
  • Dla każdego $i$ takiego, że $0 \le i < w$, tworzony jest plik o nazwie równej $S$, w którym ostatni element jest zastąpiony przez XOR z $2^i$. Jeśli plik o tej samej nazwie już istnieje, nie jest tworzony.
• Po zakończeniu wklejania wszystkie zaznaczone pliki są odznaczane.

Na przykład, gdy $w=2$, a w folderze jest tylko jeden plik $[0]$, zawartość folderu po kolejnych operacjach kopiuj-wklej zmienia się następująco:

• Początkowo: $[0]$
• Po 1. operacji: $[0]$, $[0, 0]$, $[1]$, $[2]$
• Po 2. operacji: $[0]$, $[0, 0]$, $[0, 0, 0]$, $[0, 1]$, $[0, 2]$, $[1]$, $[1, 0]$, $[2]$, $[2, 0]$, $[3]$

Minggu, mistrz kopiuj-wklej, zadał wam następujący problem. Mając początkowo w folderze tylko plik $[0]$, po wykonaniu K operacji kopiuj-wklej, jaka jest pozycja w porządku leksykograficznym pliku o nazwie A podanej przez Minggu?

Dla Minggu obliczcie pozycję A w porządku leksykograficznym modulo $998\,244\,353$!

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite w, K oddzielone spacją. ($1 \le w \le 60$; $1 \le K \le 100\,000$)

Drugi wiersz zawiera długość N szukanej nazwy pliku A. ($1 \le N \le 100\,000$)

Trzeci wiersz zawiera elementy A – A_i dla $1 \le i \le N$, oddzielone spacjami.

Dane wejściowe gwarantują, że plik o nazwie A istnieje po K operacjach kopiuj-wklej.

Wyjście

Przyjmując, że pierwszy plik w porządku leksykograficznym ma pozycję $1$, wypisz pozycję A w porządku leksykograficznym modulo $998\,244\,353$.

Przykład

Wejście 1

2 2
3
0 0 0

Wyjście 1

3

Wejście 2

2 2
1
3

Wyjście 2

10

Wejście 3

60 2024
4
998244353 1000000007 3141592653 2718281828

Wyjście 3

62474228

Uwagi

Mówimy, że ciąg $a = [a_1, a_2, \dots, a_n]$ jest wcześniejszy leksykograficznie niż ciąg $b = [b_1, b_2, \dots, b_m]$, jeśli istnieje dodatnia liczba całkowita $i$ spełniająca wszystkie poniższe warunki:

• Dla każdej dodatniej liczby całkowitej $j$ mniejszej od $i$, zarówno $a_j$ jak i $b_j$ istnieją oraz $a_j = b_j$;
• $b_i$ istnieje;
• $a_i$ nie istnieje lub $a_i < b_i$.