该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile2526.zip](file://AdditionalFile2526.zip?type=additional_file)

#2526. 「HAOI2018」苹果树

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

小 C 在自己家的花园里种了一棵苹果树，树上每个结点都有恰好两个分支。经过细心的观察，小 C 发现每一天这棵树都会生长出一个新的结点。

第一天的时候, 果树会长出一个根结点，以后每一天，果树会随机选择一个当前树中没有长出过结点的分支， 然后在这个分支上长出一个新结点，新结点与分支所属的结点之间连接上一条边。

小 C 定义一棵果树的不便度为树上两两结点之间的距离之和，两个结点之间的距离定义为从一个点走到另一个点的路径经过的边数。

现在他非常好奇，如果 $N$ 天之后小 G 来他家摘苹果，这个不便度的期望 $E$ 是多少。但是小 C 讨厌分数，所以他只想知道 $E \times N!$ 对 $P$ 取模的结果，可以证明这是一个整数。

输入格式

一行两个整数 $N, P$。

输出格式

输出一个整数表示答案。

样例 1

输入

3 610745795

输出

24

样例 2

输入

305 1000000007

输出

865018107

数据范围与提示

对于 $20\%$ 的数据，$N \le 10$；

对于 $50\%$ 的数据，$N \le 500$；

对于另外 $20\%$ 的数据，$P = 10^9 + 7$；

对于 $100\%$ 的数据，$N \le 2000, P \le 10^9 + 7$。