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$.