Minggu, qui n'a rien à faire, joue au jeu du copier-coller ! Ce jeu consiste à observer les noms des fichiers créés lors du copier-coller.

Le nom d'un fichier est une séquence de nombres entiers compris entre $0$ et $2^w-1$ (inclus), de longueur au moins $1$. Un copier-coller s'effectue comme suit :

• Étape de copie : on sélectionne tous les fichiers présents dans le dossier.
• Étape de collage : pour chaque fichier sélectionné $S$, on répète ce qui suit (les fichiers nouvellement créés ne sont pas sélectionnés) :
  • On crée un fichier dont le nom est $S$ suivi de $0$, sauf si un fichier de ce nom existe déjà.
  • Pour tout $i$ tel que $0 \le i < w$, on crée un fichier dont le nom est obtenu en faisant un XOR de $2^i$ avec le dernier élément de $S$, sauf si un fichier de ce nom existe déjà.
• Une fois l'étape de collage terminée, on désélectionne tous les fichiers qui étaient sélectionnés.

Par exemple, pour $w=2$, si le dossier ne contient initialement que le fichier $[0]$, les copier-coller successifs modifient le contenu du dossier comme suit :

• Situation initiale : $[0]$
• Après 1 opération : $[0]$, $[0, 0]$, $[1]$, $[2]$
• Après 2 opérations : $[0]$, $[0, 0]$, $[0, 0, 0]$, $[0, 1]$, $[0, 2]$, $[1]$, $[1, 0]$, $[2]$, $[2, 0]$, $[3]$

Minggu, expert en copier-coller, vous pose le problème suivant : sachant que le dossier ne contient initialement que le fichier $[0]$, après $K$ copier-coller, quel est le rang du fichier de nom $A$ fourni par Minggu dans l'ordre lexicographique ?

Pour aider Minggu, calculez le rang de $A$ dans l'ordre lexicographique modulo $998\,244\,353$.

Entrée

La première ligne contient deux entiers w et K séparés par une espace. ($1 \le w \le 60$ ; $1 \le K \le 100\,000$)

La deuxième ligne contient la longueur N du nom A du fichier recherché. ($1 \le N \le 100\,000$)

La troisième ligne contient les éléments A_i de A ($1 \le i \le N$) séparés par des espaces.

Le fichier de nom A existe toujours après $K$ copier-coller dans les données fournies en entrée.

Sortie

En considérant que le fichier le plus petit dans l'ordre lexicographique a le rang $1$, affichez le rang de A dans l'ordre lexicographique modulo $998\,244\,353$.

Exemples

Entrée 1

2 2
3
0 0 0

Sortie 1

3

Entrée 2

2 2
1
3

Sortie 2

10

Entrée 3

60 2024
4
998244353 1000000007 3141592653 2718281828

Sortie 3

62474228

Remarque

On dit qu'une séquence $a = [a_1, a_2, \cdots, a_n]$ est lexicographiquement plus petite qu'une séquence $b = [b_1, b_2, \cdots, b_m]$ s'il existe un entier positif $i$ satisfaisant toutes les conditions suivantes :

• Pour tout entier positif $j$ strictement inférieur à $i$, $a_j$ et $b_j$ existent tous deux et $a_j = b_j$ ;
• $b_i$ existe ;
• $a_i$ n'existe pas ou $a_i < b_i$.