AT_ajo2024_final_c.Final Exam

AtCoder 君参加了一场由 $n$ 道题目组成的测试。在这场测试中，题目会依次被出题，每一题的难度会根据当前的答题情况发生变化，具体规则如下：

• 如果当前的正确数大于等于错误数，那么 AtCoder 君以概率 $1/3$ 正确回答下一题。
• 如果当前的正确数小于错误数，那么 AtCoder 君以概率 $2/3$ 正确回答下一题。
• 此外，假定每题答对或答错的概率都是独立的。也就是说，每次解题时，都以概率 $1/3$ 或 $2/3$ 掷一次硬币，若正面朝上则答对。

只要答对超过一半的题目，就算合格。

现在，记 AtCoder 君合格的概率为 $f(n)$，其中 $f(n)$ 是 $3^n$ 倍的整数。

给定一个整数 $N$，请计算 $\sum_{n=1}^N \left\lfloor \frac{10^{18}}{n} \right\rfloor \times f(n)$ 模 $10^9 + 7$ 的结果，并输出。

输入包含一行，为：

$N$

输出一行，为所求答案。

样例解释 1

当题数为 $1$ 时，合格概率为 $\frac{1}{3}$；题数为 $2$ 时，合格概率为 $\frac{1}{9}$，因此：

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

对 $10^9 + 7$ 取余后，输出 $500\,000\,077$。

数据范围

• $1 \leq N \leq 10\,000\,000$
• $N$ 是整数。

由 ChatGPT 5 翻译