UOJ Logo

NOI.AC

1S 512MB

#70. 量子二叉堆

Statistics

量子二叉堆

【问题描述】

8012年,有试验舱主导的量子二叉堆研发到了最终测试阶段。他们需要知道n 个互不相同的数能构成多少个不同的大小为 n 的二叉堆,才能完成同态测量。于是SR给了你如下的参考说明,并要求你解决该问题:

Tips:完全二叉树是一种二叉树,满足除最后一层外的每层结点都是满的,且最后一层的结点连续集中在左方。二叉堆是一种完全二叉树,分为大根堆和小根堆,大根堆满足父结点的值不小于子结点的值,小根堆满足父结点的值不大于子结点的值。

最后希望你给出n个互不相同的数能构成多少个不同的大小为n的二叉堆(大根堆或小根堆都算二叉堆,不同定义为至少有一个位置上数不同)。

【输入格式】

第一行包含一个整数 n。

【输出格式】

第一行包含一个整数,表示能构成的二叉堆个数模 $10^9$ + 7后的答案。

【输入样例】

3

【输出样例】

4

【数据规模】

对于 30% 的数据, n ≤ 10。

对于 60% 的数据, n ≤ 1000。

对于 80% 的数据, n ≤ $10^5$。

对于 100% 的数据, 1 ≤ n ≤ 5 × $10^6$。