2023 年上海市大学生程序设计竞赛 - 七月赛

E. 研究方向

单点时限: 2.0 sec

内存限制: 512 MB

刚刚踏上了学术界,你开始寻找自己的研究方向。你对普通的研究方向提不起兴趣,于是你开始研究起了”研究方向”。

具体来说,一个研究方向是一个三元组 $(i,j,k)$ 表示《受到方法 $i$ 的启发,通过方法 $k$ 解决/改进 了方法 $j$ 》

比如
《Does a Program Yield the Right Distribution? Verifying Probabilistic Programs via Generating Functions》
- $i=$”Generating Functions”
- $j=$”Right Distribution?”
- $k=$”Verifying Probabilistic Programs”
《NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis.》
- $i=$”Neural Network”
- $j=$”View Synthesis”
- $k=$”Radiance Fields”


给定一个研究方向 $(i,j,k)$, 为了解决问题 $j$, 你可以以任意顺序执行以下任意操作任意次(包括 0 次):

  1. 给 $i$ 加上 $k$。(improve)
  2. 把 $i$ 变为其任意一个正整数因子。即 $i \leftarrow d$ 其中 $d>0$, 且 $d|i$。(reduce)

你发现,如果可以用以上操作将 $i$ 变成 $j$,那么研究方向$(i,j,k)$或许就是可行的。

$$
f(i,j,k) = \begin{cases} 1 & \text{you can transform } i \text{ to } j \text{ by the operations 1. and 2. } \\ 0 & \text{otherwise}\end{cases}
$$

目前,世界上总共有 $N$ 种”方法”。那么世界上究竟有多少种或许可行研究方向呢?答案是

$$
W=\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N f(i,j,k)
$$

对于每一个 $N$, 你希望计算出 $W$ 的具体数值,来搞明白世界上究竟有多少种或许可行的研究方向。因为这个数值可能过于巨大,请输出 $W \text{ mod } 10^9 + 7$ 取模的值。

输入格式

一行一个正整数$N\ (1\le N \le 10^{10})$,代表”方法”的数量。

输出格式

一行一个正整数$W\%(10^9 + 7)$,保证$W\not \equiv 0 \mod (10^9+7)$

样例

Input
2
Output
7
Input
3
Output
23
Input
123
Output
1368487

提示

当$N=2$时,只有研究方向$(1,2,2)$不可行。