#2316. [Jsoi2013]游戏中的学问

[Jsoi2013]游戏中的学问

Description

大家应该都见过很多人手拉手围着篝火跳舞的场景吧?一般情况下,大家手 拉手跳舞总是会围成一个大圈,每个人的左手拉着旁边朋友的右手,右手拉着另 一侧朋友的左手。 不过,如果每一个人都随机的拉住两个不同人的手,然后再慢慢散开,事情 就变得有趣多了——此时大家依旧会形成圈,不过却可能会形成多个独立的圈。 当然这里我们依然要求一个人的右手只能拉另一个人的左手,反之亦然。 班里一共有N个同学,由1到N编号。Will想知道,究竟有多少种本质不 同的拉手方案,使得最终大家散开后恰好形成k个圈呢? 给定两种方案,若存在一个人和他的一只手,满足在这两种方案中,拉着这 只手的人的编号不同,则这两种方案本质不同。

Format

Input

输入一行包含三个正整数N,k和P. 3<=3k<=N<=3000,10^4<=p<=2×10^9

Output

输出文件的包含一行一个整数,表示本质不同的方案数对p的余数。保证p 一定是一个质数。

Samples

3 1 1000000009
2