Avoid XOR Zero

Busy Beaver nazywa tablicę $N$ nieujemnych liczb całkowitych $A_1, A_2, \dots, A_N$ nieuniknioną, jeśli spełniony jest następujący warunek:

• Dla każdej pary tablic $(B_1, B_2, \dots, B_N)$, $(C_1, C_2, \dots, C_N)$, gdzie $B_i, C_i$ są nieujemnymi liczbami całkowitymi takimi, że $B_i + C_i = A_i$ dla każdego $i$ od $1$ do $N$, zachodzi następujący warunek:
  • Istnieje tablica $(X_1, X_2, \dots, X_N)$ taka, że dla każdego $i$, $X_i = B_i$ lub $X_i = C_i$, oraz $X_1 \oplus X_2 \oplus \dots \oplus X_N = 0$.

Tutaj $\oplus$ oznacza operację bitowej alternatywy wykluczającej (XOR).

Dane są liczby $N, K$. Znajdź liczbę nieuniknionych tablic o długości $N$, w których $0 \le A_i \le 2^K - 1$ dla wszystkich $i$. Ponieważ liczba ta może być bardzo duża, wyprowadź ją modulo pewna liczba pierwsza $P$.

Wejście

Jedyna linia każdego przypadku testowego zawiera trzy liczby całkowite $N, K, P$ ($1 \le N, K \le 100$, $10^8 < P < 10^9$, $P$ jest liczbą pierwszą).

Wyjście

Wyprowadź pojedynczą liczbę całkowitą: liczbę nieuniknionych tablic o długości $N$, w których $0 \le A_i \le 2^K - 1$ dla wszystkich $i$.

Przykłady

Wejście 1

10 1 111111113

Wyjście 1

1024

Wejście 2

14 2 263652251

Wyjście 2

237

Wejście 3

100 100 998244353

Wyjście 3

914574519

Uwagi

Dla pierwszego przykładu wszystkie tablice z elementami w $\{0, 1\}$ są nieuniknione (spróbuj samodzielnie zrozumieć dlaczego), więc istnieje ich $2^{10}$ dla długości $10$.