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$ 为非负整数且满足对于所有 $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$ 表示按位异或运算。

给定数字 $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}$ 个。