問題文

AtCoder さんは、n 問の問題からなるテストを受験しました。 このテストでは、1 問ずつ問題が出題されていきますが、出題される問題の難易度は現時点での正解状況に応じて変化し、具体的には以下のようになります。

• 現時点の正解数が、現時点での不正解数以上である場合、AtCoder さんは確率 1/3 で次の問題に正解する。
• 現時点の正解数が、現時点での不正解数未満である場合、AtCoder さんは確率 2/3 で次の問題に正解する。
• ここで、各問題の正解・不正解の確率は独立であると仮定する。すなわち、問題を解くときに確率 1/3 あるいは確率 2/3 で表が出るコインを振り、表が出たら正解すると考えて良い。

過半数の問題に正解すれば合格です。

さて、AtCoder さんが合格する確率を 3^n 倍した値 f(n) は整数になります。

整数 N が与えられるので、 \sum_{n=1}^{N} \lfloor \frac{10^{18}}{n} \rfloor \times f(n) を 10^9 + 7 で割った余りを計算してください。

制約

• 1 \leq N \leq 10\,000\,000
• N は整数

入力例 1

2

出力例 1

500000077

問題数が 1 問のときの合格確率は \frac{1}{3}、2 問のときの合格確率は \frac{1}{9} であるため、

• \lfloor \frac{10^{18}}{1} \rfloor \times \left(\frac{1}{3} \times 3^1\right) + \lfloor \frac{10^{18}}{2} \rfloor \times \left(\frac{1}{9} \times 3^2\right) = 1.5 \times 10^{18}

を 10^9 + 7 で割った余りである 500\,000\,077 を出力します。

入力例 2

1848668

出力例 2

869120830

入力例 3

10000000

出力例 3

787995111