负责人

• CFCOI_official
• zhangruixiang
• Hamburger999
• 035966_L3

注意

本题需要使用文件读写（trees.in / trees.out）。

本题中使用 $\bm{\{(a_1,b_1),(a_2,b_2),\ldots,(a_{n-1},b_{n-1})\}}$ 来表示一棵 $\bm n$ 个结点的有根树（$\bm 1$ 号结点为根），其中 $\bm{(a_i,b_i)\ (a_i<b_i)}$ 表示 $\bm{a_i}$ 号结点和 $\bm{b_i}$ 号结点之间有一条无向边。特别地，$\bm{\{\}}$ 表示一棵 $\bm 1$ 个结点的有根树。

两棵树 $\bm{\{(a_1,b_1),(a_2,b_2),\ldots,(a_{n-1},b_{n-1})\}}$ 和 $\bm{\{(c_1,d_1),(c_2,d_2),\ldots,(c_{n-1},d_{n-1})\}}$ 本质不同，当且仅当集合 $\bm{\{(a_1,b_1),(a_2,b_2),\ldots,(a_{n-1},b_{n-1})\}}$ 和 $\bm{\{(c_1,d_1),(c_2,d_2),\ldots,(c_{n-1},d_{n-1})\}}$ 不相等。

定义一棵树上某个结点的大小等于以其为根的子树（包括该结点本身）中结点的总个数。

定义一棵树的大小等于其根结点的大小。

题目描述

对于一颗以 $1$ 号结点为根的有根树，称这棵树为「平衡树」，当且仅当对于任何结点：

• 它的父亲（如果有）的结点编号小于它本身的编号。
• 它的所有儿子（如果有）的大小相等。

例如，$\{(1, 2), (2, 4), (2, 6), (2, 8), (1, 3), (3, 5), (5, 7), (5, 9)\}$ 就是一棵大小为 $9$ 的「平衡树」。

试求出大小不超过 $n$ 的本质不同的「平衡树」的数量，答案对 $10^9 + 7$ 取模。

输入格式

一行一个正整数 $n\ (1 \le n \le 10^6)$。

输出格式

一行一个非负整数表示答案。

答案对 $10^9 + 7$ 取模。

样例

1

1

2

2

3

4

4

7

5

14

样例解释

大小不超过 $5$ 的本质不同的「平衡树」有：

• $\{\}$
• $\{(1,2)\}$
• $\{(1,2),(1,3)\}$
• $\{(1,2),(2,3)\}$
• $\{(1,2),(1,3),(1,4)\}$
• $\{(1,2),(2,3),(2,4)\}$
• $\{(1,2),(2,3),(3,4)\}$
• $\{(1,2),(1,3),(1,4),(1,5)\}$
• $\{(1,2),(1,3),(2,4),(3,5)\}$
• $\{(1,2),(1,3),(2,5),(3,4)\}$
• $\{(1,2),(1,4),(2,3),(4,5)\}$
• $\{(1,2),(2,3),(2,4),(2,5)\}$
• $\{(1,2),(2,3),(3,4),(3,5)\}$
• $\{(1,2),(2,3),(3,4),(4,5)\}$