Avoid XOR Zero

一個包含 $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$ 為非負整數且對於所有 $1 \le i \le N$ 皆滿足 $B_i + C_i = A_i$，下列條件成立：
  • 存在一個陣列 $(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$ 代表位元互斥或（bitwise XOR）運算。

給定數字 $N$ 與 $K$。請找出長度為 $N$ 且對於所有 $i$ 皆滿足 $0 \le A_i \le 2^K - 1$ 的不可避免陣列的數量。由於此數字可能非常大，請輸出其對某個質數 $P$ 取模後的結果。

輸入格式

每一測試案例僅包含一行，含有三個整數 $N, K, P$ ($1 \le N, K \le 100$, $10^8 < P < 10^9$, $P$ 為質數)。

輸出格式

輸出一個整數：長度為 $N$ 且對於所有 $i$ 皆滿足 $0 \le A_i \le 2^K - 1$ 的不可避免陣列的數量。

範例

輸入 1

10 1 111111113

輸出 1

1024

輸入 2

14 2 263652251

輸出 2

237

輸入 3

100 100 998244353

輸出 3

914574519

說明

對於第一個範例，所有元素皆在 $\{0, 1\}$ 中的陣列都是不可避免的（試著自己找出原因），因此長度為 10 的陣列共有 $2^{10}$ 個。