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{array}{ll}1& \text{you can transform }i\text{ to }j\text{ by the operations 1. and 2. }\\ 0& \text{otherwise}\end{array}$$

目前，世界上总共有 $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$ 取模的值。