19458번 - Expected LCP 다국어

문제

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

제한

힌트

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