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