P9108 [PA 2020] Malowanie płotu

**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 4 [Malowanie płotu](https://sio2.mimuw.edu.pl/c/pa-2020-1/mal/)** 今年的秋季天气已经完全破坏了 Potyczek 先生的围栏上的漆。围栏需要尽快用特殊的蓝色防水剂进行处理，以免即将到来的冬季对其造成不可弥补的破坏。Potyczek 先生请他邻居的勤劳儿子 Bytie 来做这件事。这个男孩今天早上完成了任务，但做得相当粗心，因为他急着参加下一轮 PA。 Potyczek 先生的围栏由 $n$ 根木条组成，每根木条分为长度相等的 $m$ 段。Bytie 只把每根木条从上到下用防水剂涂了一遍，不幸的是，这可能还不足以把栅栏全部涂满。然而，在每根木条上涂防水剂的段都是连续的，每个段要么完全涂上，要么根本不涂。进一步看来，男孩所涂的那部分栅栏是一致的，即每两个连续的木条上所涂的段都存在一个非空的相交区间。 例如，涂完的围栏可能如下图所示。  由于以下三个原因，下图所示情况是不可能的。 - 编号为 $1$ 的木条根本没涂防水剂。 - 编号为 $3$ 的木条一致的段没有涂防水剂。 - 编号 $5,6$ 的木条涂防水剂的部分相交区间为空。  编写一个程序，计算 Bytie 按照上述规则可以用多少种不同的方式来涂围栏。如果有一段围栏在其中一种方式中被涂上了颜色，而在另一种方式中没有被涂上颜色，那么就称这两种方式是不同的。方法的数量可能相当多，所以只要输出它除以质数 $p$ 的余数就可以了。

输入一行三个整数 $n,m,p$。分别表示木条个数，每根木条上段的个数和质数 $p$。

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

#### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据，保证 $1\le n\times m\le 10^7$，$10^8\le p\le 10^9$，$p\in \mathbb{P}$。