Busy Beaver appelle un tableau de $N$ entiers non négatifs $A_1, A_2, \dots, A_N$ inévitable si la condition suivante est vérifiée :

• Pour toute paire de tableaux $(B_1, B_2, \dots, B_N)$, $(C_1, C_2, \dots, C_N)$, où $B_i, C_i$ sont des entiers non négatifs tels que $B_i + C_i = A_i$ pour tout $i$ de $1$ à $N$, la condition suivante est vérifiée :
  • Il existe un tableau $(X_1, X_2, \dots, X_N)$ tel que pour tout $i$, $X_i = B_i$ ou $X_i = C_i$, et $X_1 \oplus X_2 \oplus \dots \oplus X_N = 0$.

Ici, $\oplus$ désigne l'opération XOR bit à bit.

Vous recevez les nombres $N, K$. Trouvez le nombre de tableaux inévitables de longueur $N$, dans lesquels $0 \le A_i \le 2^K - 1$ pour tout $i$. Comme ce nombre peut être très grand, donnez-le modulo un nombre premier $P$.

Entrée

La seule ligne de chaque cas de test contient trois entiers $N, K, P$ ($1 \le N, K \le 100$, $10^8 < P < 10^9$, $P$ est premier).

Sortie

Affichez un seul entier : le nombre de tableaux inévitables de longueur $N$, dans lesquels $0 \le A_i \le 2^K - 1$ pour tout $i$.

Exemples

Entrée 1

10 1 111111113

Sortie 1

1024

Entrée 2

14 2 263652251

Sortie 2

237

Entrée 3

100 100 998244353

Sortie 3

914574519

Remarque

Pour le premier exemple, tous les tableaux avec des éléments dans $\{0, 1\}$ sont inévitables (essayez de voir pourquoi par vous-même), il y en a donc $2^{10}$ de longueur $10$.