#2745. [HEOI2012]Bridge

题目描述

fyg背着他的电脑来到河北省来，就是为了见一眼古老的赵州桥。
终于，他来到了赵州桥，放下了电脑，正准备休息。一阵风吹来，从中闪现出一人影。fyg只觉天昏地暗，待得再次睁开眼时，发觉自己已经到了一神奇的国度，置身于一巨大的圆盘之上。放眼看去，四周都是奇形怪状的桥，不远处有一老头盘膝而坐。 fyg还沉浸在惊奇之中，老头（难道就是传说中走过赵州桥的张老头！！）便开口了：凡人，你现在在我的世界中，想要出去就要回答我的问题。fyg只得点头，老头继续道：你现在要去闯关，我给你m种颜色，总共有n关（神仙也懂数学，表示压力巨大。。==）。每一关中有一座桥，在第i关中，桥长度有i个单位，每个单位长度上有2个格子（也就是说这座桥有2i个格子），现在你要计算出：在这座桥上涂色使得桥上相邻格子的颜色不一样总方案数，然后再乘上（2i）^m。如在第1关，若你手上有2种颜色，分别为蓝色和绿色。则总方案数为22*2 =8种，涂色方案数为2（如下图，旋转、翻转相同算不同的方案），然后还要再乘2个2，最后你出来之后我会问你所有关中计算出来的数的和。如果你能答对，我就可以让你出去了，否则就无限轮回吧。
fyg表示这个问题太水了，完全不想算。。。于是， 他马上打开电脑上了QQ找到了喜欢计算的你，求你 帮他直接把最终 答案算出来，让他回到赵州桥上。这两个数都有可能很大，fyg 不想为难你，所以你只要告诉他其除以p的余数。

输入格式

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

输出格式

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

样例

样例输入

2  5 50  

样例输出

30   

【样例说明】   

总共有2关。   

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

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

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

数据范围与提示

【数据范围】

对于其中25%的数据，满足 n <= 10^6，m <= 200，p <= 10^9； 对于其中40%的数据，满足 n <= 10^9，m <= 120，p <= 10^9； 对于其中15%的数据，满足 n <= 10^9，m <= 200，p <= 10^9； 对于最后20%的数据，满足 n<= 10^9，m <= 3000，p <= 3000；