AT_ajo2024_final_c Final Exam

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 $ で割った余りを計算してください。

入力は以下の形式で標準入力から与えられます。 > $ N $

答えを出力してください。

### Sample Explanation 1 問題数が $ 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 $ を出力します。 ### Constraints - $ 1 \leq N \leq 10\,000\,000 $ - $ N $ は整数