1391 - コンピューターシステムの不具合

問題

あなたは世界最高性能のコンピュータシステム「那由多（なゆた）」を設計している。しかし、このシステムのプロトタイプの実装中に、命令列がある条件を満たすとシステムが停止するという不具合が見つかった。

このシステムは、長さ$N$の命令列をプログラムとして与えることで動作する。命令列の中の$m$番目の命令を数$X_m$で表したとき、不具合が起こる条件は、ある整数$i,j$ ($2 \leq i＜j \leq N$)に対して$X_i + X_{j-1} = X_j + X_{i-1}$となる命令のパターンが命令列に存在することであると判明した。

あなたはこの不具合がどの程度の影響になるのかを調べるため、ある長さで作ることができる命令列のうち、何種類の命令列が不具合を起こすかを調べることにした。

長さ$N$の命令列のうち、不具合が起こる命令列が何通りあるかを求めるプログラムを作成せよ。ただし、命令は$1$以上$K$以下の整数で表せることとする。答えは与えられた素数$M$で割った余りとする。

入力

入力は以下の形式で与えられる。

$N$ $K$ $M$

１行に、命令列の長さ$N$ ($3 \leq N \leq 100,000$)、命令の種類の数$K$ ($1 \leq K \leq 10$)、素数$M$ ($100,000,007 \leq M \leq 1,000,000,007$)が与えられる。

出力

不具合を起こす命令列の数をMで割った余りを出力する。

入出力例

入力例１

3 2 100000007

出力例１

2

命令列を$(X_1,X_2,X_3)$のように表すと、考えられる命令列は$(1,1,1)$、$(1,1,2)$、$(1,2,1)$、$(1,2,2)$、$(2,1,1)$、$(2,1,2)$、$(2,2,1)$、$(2,2,2)$の８通り。このうち、不具合が起こる命令列は$(1,1,1)$、$(2,2,2)$の２通り。

入力例２

9 10 100000037

出力例２

66631256

不具合が起こる命令列は866631552通りあるが、その数を素数100000037で割った余りが出力となる。