Busy Beaver называет массив из $N$ неотрицательных целых чисел $A_1, A_2, \dots, A_N$ «неизбежным» (unavoidable), если выполняется следующее условие:

• Для любой пары массивов $(B_1, B_2, \dots, B_N)$ и $(C_1, C_2, \dots, C_N)$, где $B_i, C_i$ — неотрицательные целые числа, такие что $B_i + C_i = A_i$ для всех $i$ от $1$ до $N$, выполняется следующее условие:
  • Существует массив $(X_1, X_2, \dots, X_N)$ такой, что для каждого $i$, $X_i = B_i$ или $X_i = C_i$, и $X_1 \oplus X_2 \oplus \dots \oplus X_N = 0$.

Здесь $\oplus$ обозначает операцию побитового исключающего ИЛИ (XOR).

Вам даны числа $N, K$. Найдите количество неизбежных массивов длины $N$, в которых $0 \le A_i \le 2^K - 1$ для всех $i$. Поскольку это число может быть очень большим, выведите его по модулю некоторого простого числа $P$.

Входные данные

Единственная строка каждого теста содержит три целых числа $N, K, P$ ($1 \le N, K \le 100$, $10^8 < P < 10^9$, $P$ — простое число).

Выходные данные

Выведите единственное целое число: количество неизбежных массивов длины $N$, в которых $0 \le A_i \le 2^K - 1$ для всех $i$.

Примеры

Примечание

Для первого примера все массивы с элементами из $\{0, 1\}$ являются неизбежными (попробуйте понять почему самостоятельно), поэтому существует $2^{10}$ таких массивов длины $10$.