Busy Beaver は、$N$ 個の非負整数からなる配列 $A_1, A_2, \dots, A_N$ が以下の条件を満たすとき、それを「回避不可能 (unavoidable)」と呼ぶ。

• すべての $i$ ($1 \le i \le N$) に対して $B_i + C_i = A_i$ を満たす非負整数の組 $(B_1, B_2, \dots, B_N)$ および $(C_1, C_2, \dots, C_N)$ のすべてのペアに対して、以下の条件が成り立つ。
  • すべての $i$ に対して $X_i = B_i$ または $X_i = C_i$ であり、かつ $X_1 \oplus X_2 \oplus \dots \oplus X_N = 0$ を満たす配列 $(X_1, X_2, \dots, X_N)$ が存在する。

ここで、$\oplus$ はビットごとの XOR 演算を表す。

$N$ と $K$ が与えられる。すべての $i$ について $0 \le A_i \le 2^K - 1$ を満たす長さ $N$ の回避不可能な配列の個数を求めよ。この数は非常に大きくなる可能性があるため、ある素数 $P$ で割った余りを出力せよ。

入力

各テストケースの入力は1行のみであり、3つの整数 $N, K, P$ が含まれる ($1 \le N, K \le 100$, $10^8 < P < 10^9$, $P$ は素数)。

出力

すべての $i$ について $0 \le A_i \le 2^K - 1$ を満たす長さ $N$ の回避不可能な配列の個数を、単一の整数として出力せよ。

入出力例

入力 1

10 1 111111113

出力 1

1024

入力 2

14 2 263652251

出力 2

237

入力 3

100 100 998244353

出力 3

914574519

注記

最初のサンプルについて、要素が $\{0, 1\}$ であるすべての配列は回避不可能である（なぜそうなるか考えてみよ）。したがって、長さ 10 の配列は $2^{10}$ 通り存在する。