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