시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 256 MB2517861.538%

## 문제

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

2

1

3

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