量子二叉堆

【问题描述】

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$。