¡Minggu, que no tiene nada que hacer, está jugando al juego de copiar y pegar! El juego de copiar y pegar consiste en observar los nombres que se generan al copiar y pegar archivos.

El nombre de un archivo es una secuencia de enteros de longitud al menos $1$, donde cada entero es mayor o igual que $0$ y menor que $2^w$. Una operación de copiar y pegar se realiza mediante el siguiente procedimiento:

• Proceso de copia: se seleccionan todos los archivos en la carpeta.
• Proceso de pegado: para cada archivo seleccionado $S$, se repite lo siguiente (los archivos recién creados no se seleccionan):
  • Se crea un archivo cuyo nombre es $S$ con un $0$ añadido al final. No se crea si ya existe un archivo con el mismo nombre.
  • Para todo $i$ con $0 \le i \lt w$, se crea un archivo cuyo nombre es el obtenido al aplicar XOR con $2^i$ al último elemento de $S$. No se crea si ya existe un archivo con el mismo nombre.
• Una vez terminado el proceso de pegado, se deseleccionan todos los archivos seleccionados.

Por ejemplo, si $w=2$ y la carpeta contiene inicialmente solo el archivo $[0]$, al repetir las operaciones de copiar y pegar, el contenido de la carpeta cambia de la siguiente manera:

• Situación inicial: $[0]$
• 1 vez: $[0]$, $[0, 0]$, $[1]$, $[2]$
• 2 veces: $[0]$, $[0, 0]$, $[0, 0, 0]$, $[0, 1]$, $[0, 2]$, $[1]$, $[1, 0]$, $[2]$, $[2, 0]$, $[3]$

Minggu, experto en copiar y pegar, les ha propuesto el siguiente problema: si la carpeta contiene inicialmente solo el archivo $[0]$, después de K operaciones de copiar y pegar, ¿en qué posición lexicográfica se encuentra el archivo cuyo nombre es A que Minggu les da?

¡Ayuden a Minggu calculando el orden de A en orden lexicográfico módulo $998\,244\,353$!

Entrada

La primera línea contiene los enteros w, K separados por un espacio. ($1 \le w \le 60$; $1 \le K \le 100\,000$)

La segunda línea contiene la longitud N del nombre del archivo A que se busca. ($1 \le N \le 100\,000$)

La tercera línea contiene los elementos A_i de A separados por espacios, para $1 \le i \le N$.

Se garantiza que el archivo con nombre A existe después de K operaciones de copiar y pegar.

Salida

Considerando que el archivo lexicográficamente más pequeño tiene orden $1$, imprime el resto de dividir el orden de A en orden lexicográfico por $998\,244\,353$.

Ejemplos

Entrada 1

2 2
3
0 0 0

Salida 1

3

Entrada 2

2 2
1
3

Salida 2

10

Entrada 3

60 2024
4
998244353 1000000007 3141592653 2718281828

Salida 3

62474228

Nota

Se dice que la secuencia $a = [a_1, a_2, \cdots, a_n]$ es lexicográficamente menor que la secuencia $b = [b_1, b_2, \cdots, b_m]$ si existe un entero positivo $i$ que satisface todo lo siguiente:

• Para todo entero positivo $j$ menor que $i$, tanto $a_j$ como $b_j$ existen y $a_j = b_j$.
• $b_i$ existe.
• $a_i$ no existe o $a_i < b_i$.