시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 1 1 1 100.000%

문제

Define a random linear recursive sequence (RLRS) as a sequence of random variables $a_0, a_1, \ldots$ which is generated as follows. First, $a_0 = 1$. Then, for every $n$ starting from $1$, choose integers $i$ and $j$ independently and equiprobably from $[0; n-1]$, and set $a_n = a_i + a_j$ (note that at this moment, the values of $a_0$, $\ldots$, $a_{n - 1}$ are already determined).

For example, $a_1 = a_0 + a_0 = 2$, and $a_2$ is equally likely to be $a_0 + a_0$, $a_0 + a_1$, $a_1 + a_0$ and $a_1 + a_1$, thus it has 25% probability to be $2$, 50% to be $3$ and 25% to be $4$. After that, $a_3$ is equiprobably chosen from $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$; and so on.

You are to determine the variance of $n$-th term of RLRS.

The variance of a random variable $X$ is defined as $\mathbf{Var}(X) = \mathbf{E}(X - \mathbf{E}(X))^2$ (here $\mathbf{E}(X)$ means expectation or mean value of the random variable $X$).

입력

The first line of input contains the integer $n$ ($0 \leq n \leq 10^6$).

출력

Let the variance of $a_n$ be a rational number equal to $U/V$ when cancelled to lowest terms (that is, $U$ and $V$ are integers, $V > 0$ and the greatest common divisor of $U$ and $V$ is $1$). Output the number $X = (U \cdot V^{-1}) \bmod (10^9 + 7)$. That is, $X$ should satisfy the congruence $VX \equiv U$ modulo $(10^9 + 7)$. It is guaranteed that such $X$ exists and is the only root of this equation with $0 \leq X < 10^9 + 7$.

예제 입력 1

1

예제 출력 1

0

예제 입력 2

2

예제 출력 2

500000004

예제 입력 3

5

예제 출력 3

305555565

노트

$a_1$ is always equal to $2$, so $\mathbf{Var}(a_1) = 0$.

$\mathbf{Var}(a_2) = \frac{1}{2}$.

$\mathbf{Var}(a_5) = \frac{263}{36}$.