考虑一个包含 $n$ 个无限长二进制字符串（即仅由 0 和 1 组成）的序列 $s_1, s_2, \dots, s_n$，其中每个字符串的每个字符都是独立且均匀随机生成的。记 $$f(s_1, s_2, \dots, s_n) = \max_{1 \le i < j \le n} LCP(s_i, s_j)$$ 其中 $LCP$ 表示两个字符串的最长公共前缀长度。计算 $f(s_1, s_2, \dots, s_n)$ 的期望值。
输入仅包含一行，为一个整数 $n$ ($2 \le n \le 10^4$)。
将答案表示为最简分数 $P/Q$。输出 $P \cdot Q^{-1} \pmod{10^9 + 7}$。保证 $Q \pmod{10^9 + 7} \neq 0$。
样例
输入格式 1
2
输出格式 1
1
输入格式 2
3
输出格式 2
333333338
说明
注意期望值总是有限的，即 $E[f(s_1, \dots, s_n)] < \infty$。
在第二个样例中，答案为 $7/3$。