「PA 2020」Malowanie płotu

题目描述

今年的秋季天气已经完全破坏了 Potyczek 先生的围栏上的漆。围栏需要尽快用特殊的蓝色防水剂进行处理，以免即将到来的冬季对其造成不可弥补的破坏。Potyczek 先生请他邻居的勤劳儿子 Bytie 来做这件事。这个男孩今天早上完成了任务，但做得相当粗心，因为他急着参加下一轮 PA。

Potyczek 先生的围栏由 $n$ 根木条组成，每根木条分为长度相等的 $m$ 段。Bytie 只把每根木条从上到下用防水剂涂了一遍，不幸的是，这可能还不足以把栅栏全部涂满。然而，在每根木条上涂防水剂的段都是连续的，每个段要么完全涂上，要么根本不涂。进一步看来，男孩所涂的那部分栅栏是一致的，即每两个连续的木条上所涂的段都存在一个非空的相交区间。

例如，涂完的围栏可能如下图所示。

由于以下三个原因，下图所示情况是不可能的：

1. 编号为 $1$ 的木条根本没涂防水剂。
2. 编号为 $3$ 的木条一致的段没有涂防水剂。
3. 编号 $5,6$ 的木条涂防水剂的部分相交区间为空。

编写一个程序，计算 Bytie 按照上述规则可以用多少种不同的方式来涂围栏。如果有一段围栏在其中一种方式中被涂上了颜色，而在另一种方式中没有被涂上颜色，那么就称这两种方式是不同的。方法的数量可能相当多，所以只要输出它除以质数 $p$ 的余数就可以了。

输入格式

输入一行三个整数 $n, m, p$ ($1 \leq n \cdot m \leq 10^7, 10^8 \leq p \leq 10^9, p \in \mathbb{P}$)。分别表示木条个数，每根木条上段的个数和质数 $p$。

输出格式

输出一个整数表示 Bytie 按照上述规则给围栏涂色的方案数对 $p$ 取模后的值。

样例 1

输入

3 2 100000007

输出

17

样例 2

输入

6 9 813443923

输出

57