Description

fyg 还沉浸在惊奇之中，老头（难道就是传说中走过赵州桥的张老头！！）便开口了：凡人，你现在在我的世界中，想要出去就要回答我的问题。fyg 只得点头，老头继续道：你现在要去闯关，我给你$m$种颜色，总共有$n$关（神仙也懂数学，表示压力巨大。。==）。每一关中有一座桥，在第$i$关中，桥长度有$i$个单位，每个单位长度上有$2$个格子（也就是说这座桥有$2i$个格子），现在你要计算出：在这座桥上涂色使得桥上相邻格子的颜色不一样总方案数，然后再乘上$(2\times i)^m$。如在第$1$关，若你手上有$2$种颜色，分别为蓝色和绿色。则总 方案数为$2\times 2\times 2=8$种，涂色方案数为 2（如下图，旋转、翻转相同算不同的方案），然后 还要再乘 2 个 2，最后你出来之后我会问你所有关中计算出来的数的和。如果你能答对，我就可以让你出去了，否则就无限轮回吧。

fyg 表示这个问题太水了，完全不想算。。。于是，他马上打开电脑上了QQ找到了喜欢计算的你，求你帮他直接把最终答案算出来，让他回到赵州桥上。

这两个数都有可能很大，fyg 不想为难你，所以你只要告诉他其除以 $p$ 的余数。

Input Format

只有一行，其中包含三个正数 $n$、$m$、$p$，分别由一个空格分开。$n$、$m$、$p$ 含义和题目描述一致。

Output Format

一行，表示方案数的和除以 $p$ 的余数。

2 5 50 

30

Hint

【样例说明】

总共有 $2$ 关。

第一关的桥长度为 $1$，总共有 $2$ 个格子，涂色方案数为 $20$，再乘上 $2 ^ 5$，第一关中计算出的数为 $640$。

第二关的桥长度为 $2$，总共有 $4$ 个格子，涂色方案数为 $260$，再乘上 $4 ^ 5$，第二关中计算出的数为 $266240$。

两个数字加起来除以 $50$ 余 $30$，故输出为 $30$。

【数据范围】

对于其中 25%的数据，满足 $n\leq10^6$，$m\leq200$，$p\leq10^9$；

对于其中 40%的数据，满足 $n\leq10^9$，$m\leq120$，$p\leq10^9$；

对于其中 15%的数据，满足 $n\leq10^9$，$m\leq200$，$p \leq10^9$；

对于最后 20%的数据，满足 $n\leq10^9$，$m\leq3000$，$p\leq3000$；

HEOI 2012 Day2 Task1