Avoid XOR Zero

Busy Beaver llama a un arreglo de $N$ enteros no negativos $A_1, A_2, \dots, A_N$ inevitable si se cumple la siguiente condición:

• Para cada par de arreglos $(B_1, B_2, \dots, B_N)$, $(C_1, C_2, \dots, C_N)$, donde $B_i, C_i$ son enteros no negativos tales que $B_i + C_i = A_i$ para todo $i$ desde $1$ hasta $N$, se cumple la siguiente condición:
  • Existe un arreglo $(X_1, X_2, \dots, X_N)$ tal que para todo $i$, $X_i = B_i$ o $X_i = C_i$, y $X_1 \oplus X_2 \oplus \dots \oplus X_N = 0$.

Aquí $\oplus$ denota la operación XOR a nivel de bits.

Se le dan los números $N, K$. Encuentre el número de arreglos inevitables de longitud $N$, en los cuales $0 \le A_i \le 2^K - 1$ para todo $i$. Dado que este número puede ser muy grande, imprímalo módulo un número primo $P$.

Entrada

La única línea de cada caso de prueba contiene tres enteros $N, K, P$ ($1 \le N, K \le 100$, $10^8 < P < 10^9$, $P$ es primo).

Salida

Imprima un solo entero: el número de arreglos inevitables de longitud $N$, en los cuales $0 \le A_i \le 2^K - 1$ para todo $i$.

Ejemplos

Entrada 1

10 1 111111113

Salida 1

1024

Entrada 2

14 2 263652251

Salida 2

237

Entrada 3

100 100 998244353

Salida 3

914574519

Nota

Para el primer ejemplo, todos los arreglos con elementos en $\{0, 1\}$ son inevitables (intente ver por qué usted mismo), por lo que hay $2^{10}$ de ellos de longitud $10$.