#2745. [HEOI2012]Bridge

内存限制:128 MiB 时间限制:30 Sec

题目描述

fyg背着他的电脑来到河北省来,就是为了见一眼古老的赵州桥。
终于,他来到了赵州桥,放下了电脑,正准备休息。一阵风吹来,从中闪现出一人影。fyg只觉天昏地暗,待得再次睁开眼时,发觉自己已经到了一神奇的国度,置身于一巨大的圆盘之上。放眼看去,四周都是奇形怪状的桥,不远处有一老头盘膝而坐。 fyg还沉浸在惊奇之中,老头(难道就是传说中走过赵州桥的张老头!!)便开口了:凡人,你现在在我的世界中,想要出去就要回答我的问题。fyg只得点头,老头继续道:你现在要去闯关,我给你m种颜色,总共有n关(神仙也懂数学,表示压力巨大。。==)。每一关中有一座桥,在第i关中,桥长度有i个单位,每个单位长度上有2个格子(也就是说这座桥有2i个格子),现在你要计算出:在这座桥上涂色使得桥上相邻格子的颜色不一样总方案数,然后再乘上(2*i)^m。如在第1关,若你手上有2种颜色,分别为蓝色和绿色。则总方案数为2*2*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;