#P9108. [PA2020] Malowanie płotu

[PA2020] Malowanie płotu

题目描述

题目译自 PA 2020 Runda 4 Malowanie płotu

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

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

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

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

  • 编号为 11 的木条根本没涂防水剂。
  • 编号为 33 的木条一致的段没有涂防水剂。
  • 编号 5,65,6 的木条涂防水剂的部分相交区间为空。

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

输入格式

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

输出格式

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

3 2 100000007
17
6 9 813443923
57

提示

数据范围

本题采用捆绑测试

对于 100%100\% 的数据,保证 1n×m1071\le n\times m\le 10^7108p10910^8\le p\le 10^9pPp\in \mathbb{P}