19213번 - Fibonacci's Nightmare 다국어

문제

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

제한

노트

$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}$.