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

문제

Consider a sequence $s_1$, $s_2$, $\ldots$, $s_n$ of $n$ infinite binary strings (that is, consisting only of zeros and ones), where each character of each string is generated uniformly at random independently from others. Denote $$f(s_1, s_2, \ldots, s_n) = \max_{1 \le i < j \le n} LCP(s_i, s_j)\text{,}$$ where $LCP$ is the maximum common prefix of two strings. Compute the expected value of $f(s_1, s_2, \ldots, s_n)$.

입력

The only line of the input contains one integer $n$ ($2 \le n \le 10^4$).

출력

Let the answer in the form of an irreducible fraction be $P / Q$. Then output $P \cdot Q^{-1} \bmod (10^9 + 7)$. It is guaranteed that $Q \bmod (10^9 + 7) \neq 0$.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

3

예제 출력 2

333333338

힌트

Note that the expected value is always finite, that is, $\mathtt{E}f(s_1, \ldots, s_n) < \infty$.  

In the second sample the answer is $\frac{7}{3}$.