How to solve this problem?
Consider a sequence s1, s2, ..., sn 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(s1,s2,...,sn) = max LCP(si,sj), 1 ≤ i < j ≤ n where LCP is the maximum common prefix of two strings. Compute the expected value of f(s1, s2, . . . , sn).
The only line of the input contains one integer n (2 ≤ n ≤ 10^4).
Let the answer in the form of an irreducible fraction be P/Q. Then output P · Q^−1 mod (10^9 + 7).