#3160. [SHOI2006] 有色图

    ID: 3160 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>搜索2006各省省选上海扩展欧几里德扩欧群论置换Polya原理

[SHOI2006] 有色图

题目描述

如果一张无向完全图(完全图就是任意两个不同的顶点之间有且仅有一条边相连)的每条边都被染成了一种颜色,我们就称这种图为有色图。如果两张有色图有相同数量的顶点,而且经过某种顶点编号的重排,能够使得两张图对应的边的颜色是一样的,我们就称这两张有色图是同构的。以下两张图就是同构的,因为假如你把第一张图的顶点 (1,2,3,4)(1,2,3,4) 置换成第二张图的 (4,3,2,1)(4,3,2,1),就会发现它们是一样的。

你的任务是,对于计算所有顶点数为 nn,颜色种类不超过 mm 的图,最多有几张是两两不同构的图。由于最后的答案会很大,你只要输出结论模 pp 的余数就可以了(pp 是一个质数)。

输入格式

输入文件只有一行,由三个正整数 n,m,pn,m,p 组成。

输出格式

即总数模 pp 后的余数。

1 1 2
1
3 2 97
4
3 4 97
20

提示

对于 100%100 \% 的数据,1n531\leq n\leq 531m10001\leq m\leq 1000n<p109n<p\leq 10^9