#2526. 「HAOI2018」苹果树

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: wearry

题目描述

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

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

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

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

输入格式

一行两个整数 N, P

输出格式

输出一个整数表示答案。

样例

样例输入1

3 610745795

样例输出1

24

样例输入2

305 1000000007

样例输出2

865018107

数据范围与提示

对于 20\% 的数据, N \le 10

对于 50\% 的数据, N \le 500

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

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