题目描述

”终于投完了”，Marvolo长出了一口气，”现在就等结果了”

”不是已经钦定Eric了吗，也没有什么结果好等的”

”人呐，都不知道，自己是这样的不可预料，这会咱们能干什么？”

”之前Eric送了我一个骰子，咱们玩会骰子吧”，说着Mike掏出了一个骰子。

Mike和Marvolo在会场中玩起了扔骰子。但是这个骰子啊，非常妙，是由$m$种颜色涂成的正$m$面体。为了方便起见，这$m$种颜色被记作$1 \dots m$。突然，Mike想到一个问题：投掷$n$次色子后，第$6$种颜色恰巧出现偶数次的方案有多少种？Marvolo听到这个问题一脸茫然，不知所措。为了方便计算，Mike只要计算方案数对$p$取模的结果。

输入格式

一行，$3$个整数，分别表示$n、m、p$。

输出格式

一行，$1$个整数，表示答案对$p$取模后的值。

样例输入

ex_colorful1.in

2 6 10007

样例输出

ex_colorful1.ans

26

数据范围

对于前$50\%$组数据，有$n \leq 10^{4}$，$m \leq 10^4$且$p$为质数

对于前$70\%$组数据，有$n \leq 10^{18}$且$p$为质数

对于所有数据，有$0 < n \leq 10^{18}$，$6 \leq m \leq 10^{9}$，$2 \leq p \leq 10^{9}$

时间限制：1s

空间限制：256M

样例数据下载