定义一个随机线性递归序列 (RLRS) 为一个随机变量序列 $a_0, a_1, \dots$，其生成方式如下：首先，$a_0 = 1$。然后，对于每一个从 $1$ 开始的 $n$，独立且等概率地从 $[0, n-1]$ 中选择整数 $i$ 和 $j$，并令 $a_n = a_i + a_j$（注意此时 $a_0, \dots, a_{n-1}$ 的值已经确定）。

例如，$a_1 = a_0 + a_0 = 2$，$a_2$ 等概率地取 $a_0 + a_0, a_0 + a_1, a_1 + a_0$ 和 $a_1 + a_1$，因此它有 $25\%$ 的概率为 $2$，$50\%$ 的概率为 $3$，$25\%$ 的概率为 $4$。此后，$a_3$ 从 $a_0 + a_0, a_0 + a_1, a_0 + a_2, a_1 + a_0, a_1 + a_1, a_1 + a_2, a_2 + a_0, a_2 + a_1, a_2 + a_2$ 中等概率选择；依此类推。

你需要确定 RLRS 第 $n$ 项的方差。

随机变量 $X$ 的方差定义为 $\text{Var}(X) = \mathbf{E}(X - \mathbf{E}(X))^2$（此处 $\mathbf{E}(X)$ 表示随机变量 $X$ 的期望或平均值）。

输入格式

输入的第一行包含整数 $n$ ($0 \le n \le 10^6$)。

输出格式

设 $a_n$ 的方差为化简后的有理数 $U/V$（即 $U$ 和 $V$ 为整数，$V > 0$ 且 $U$ 和 $V$ 的最大公约数为 $1$）。输出数字 $X = (U \cdot V^{-1}) \pmod{10^9 + 7}$。即 $X$ 应满足同余式 $VX \equiv U \pmod{10^9 + 7}$。保证这样的 $X$ 存在，且是在 $0 \le X < 10^9 + 7$ 范围内该方程的唯一根。

样例

样例输入 1

1

样例输出 1

0

样例输入 2

2

样例输出 2

500000004

样例输入 3

5

样例输出 3

305555565

说明

$a_1$ 始终等于 $2$，因此 $\text{Var}(a_1) = 0$。 $\text{Var}(a_2) = \frac{1}{2}$。 $\text{Var}(a_5) = \frac{263}{36}$。