配点 : 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