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

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

具体来说，一个研究方向是一个三元组 $(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$ 取模的值。