← 返回题目列表

AtCoder · ajo2024_final_c

C. 期末考试

中文机器翻译题面 查看原题

配点 : 1000 点

問題文

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 是整数

入力

输入如下格式从标准输入给出。

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