피보나치의 악몽

무작위 선형 재귀 수열(random linear recursive sequence, RLRS)을 다음과 같이 생성되는 확률변수 수열 $a_0, a_1, \ldots$로 정의한다. 먼저 $a_0 = 1$이다. 그다음 $n = 1, 2, \ldots$ 각각에 대해 $[0; n-1]$에서 정수 $i$와 $j$를 독립적으로, 그리고 균등한 확률로 선택하고 $a_n = a_i + a_j$로 둔다. 이때 $a_0, \ldots, 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$의 분산은 $\mathbf{Var}(X) = \mathbf{E}(X - \mathbf{E}(X))^2$로 정의한다. 여기서 $\mathbf{E}(X)$는 확률변수 $X$의 기댓값 또는 평균이다.

첫 줄에 정수 $n$이 주어진다 ($0 \leq n \leq 10^6$).

$a_n$의 분산을 기약분수로 나타냈을 때 $U/V$라 하자. 즉 $U$와 $V$는 정수이고 $V > 0$이며 $U$와 $V$의 최대공약수는 $1$이다. $X = (U \cdot V^{-1}) \bmod (10^9 + 7)$을 출력한다. 다시 말해 $X$는 $10^9 + 7$을 법으로 $VX \equiv U$를 만족해야 한다. 그러한 $X$가 존재하며 $0 \leq X < 10^9 + 7$ 범위에서 유일함이 보장된다.

$a_1$은 항상 $2$이므로 $\mathbf{Var}(a_1) = 0$이다.

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

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