시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 256 MB | 32 | 22 | 12 | 70.588% |
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}$.