전염병

2202년, 인구가 $n$명인 도시에서 이상한 질병이 퍼지기 시작한다. 확산을 막기 위해 전문가들은 Mysterious Oscar라는 강력한 백신을 개발했다. 0일차에 시민 한 명이 감염되고, 다른 시민 한 명이 백신을 맞는다. 백신을 맞은 사람은 즉시 치료되며, 이후 질병에 걸리거나 질병을 퍼뜨리지 않는다. 각 날짜 $d$ ($d>0$)에는 날짜 $d$보다 전에 감염된 시민 각각이 감염되지도 않고 백신도 맞지 않은 시민 한 명을 같은 확률로 골라 감염시킨다. 감염시킬 사람이 남아 있지 않은 감염자는 아무 일도 하지 않는다. 감염 단계가 끝나면, 날짜 $d$보다 전에 백신을 맞은 시민 각각이 백신을 맞지 않은 시민 2명을 같은 확률로 골라 백신을 맞도록 설득한다. 이를 한 명씩 차례로 진행한다. 백신을 맞은 시민이 고를 수 있는 미접종 시민이 2명 미만이면, 남은 미접종 시민 전부를 설득한다. 그래미는 질병이 완전히 사라지기까지 며칠이 걸리는지 알고 싶어 한다. 모든 환자가 치료될 때까지 걸리는 날짜 수의 기댓값을 구하라.

답은 기약분수 $\frac{x}{y}$로 나타낼 수 있으며, $x$와 $y$는 정수이고 $y \not\equiv 0 \pmod{10^9+7}$이다. $x\cdot y^{-1}\pmod{10^9+7}$ 값을 출력하라. 즉, $0\leq a<10^9+7$이고 $a\cdot y\equiv x\pmod{10^9+7}$를 만족하는 정수 $a$를 출력하라.

한 줄에 정수 $n$ ($2 \leq n \leq 1.4 \cdot 10^7$)이 주어진다. 이는 도시의 인구이다.

모든 환자가 치료될 때까지 걸리는 날짜 수의 기댓값을 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.

$n=2$인 경우, 0일차에 한 명이 백신을 맞고 남은 환자 한 명을 설득해 1일차에 백신을 맞게 한다. 따라서 질병은 1일차에 완전히 사라진다.