A6709. 「HEOI2012」赵州桥

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$ 的余数。

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

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

对于其中 $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$。