[Jsoi2013]游戏中的学问
时间限制：10s 空间限制：256MB
题目描述
大家应该都见过很多人手拉手围着篝火跳舞的场景吧？一般情况下，大家手
拉手跳舞总是会围成一个大圈，每个人的左手拉着旁边朋友的右手，右手拉着另
一侧朋友的左手。
不过，如果每一个人都随机的拉住两个不同人的手，然后再慢慢散开，事情
就变得有趣多了——此时大家依旧会形成圈，不过却可能会形成多个独立的圈。
当然这里我们依然要求一个人的右手只能拉另一个人的左手，反之亦然。
班里一共有N个同学，由1到N编号。Will想知道，究竟有多少种本质不
同的拉手方案，使得最终大家散开后恰好形成k个圈呢？
给定两种方案，若存在一个人和他的一只手，满足在这两种方案中，拉着这
只手的人的编号不同，则这两种方案本质不同。
输入格式
输入一行包含三个正整数N，k和P.
3<=3k<=N<=3000，10^4<=p<=2×10^9
输出格式
输出文件的包含一行一个整数，表示本质不同的方案数对p的余数。保证p
一定是一个质数。
样例输入
3 1 1000000009
样例输出
2
提示
没有写明提示
题目来源
By 佚名上传