这题比较难，于是就来写下题解吧

公式警告

题目意思非常简明，就是让你求成立的四元组的个数，考虑如何解决

一开始，我的想法是两边同时取对化简，但是搞了很久，发现复杂度至少要n^2才可做，于是放弃了这个做法。

我们现在来考虑下其他方法。。。

首先，我们将a和c分解质因数

那么一定有:




又因为,那么分别有：

即:

意思是，a和c分解质因数后，对应的质因数的指数一定是成比例的！

那么，我们不妨设有最简分数，那么一定有：

对于任意对于任意
且,

那么，我们设


由上述关系，我们还可以得到

那么，原式就可以化为:
我们把i叫做"公共基底数"

那么，我们可以考虑枚举这个"i",因为<=n,所以我们枚举的的个数其实是很少的，可以直接计算。

假如，我们有，那么，我们将这些数两两组合（即枚举对应的a和c）

假如，我们将和组合了，那么，我们需要找到和的多少次方相等

假设,,那么有:

于是有:

那么，我们第一想法就是求k和g的lcm，因为,所以一定是的倍数。

那么我们就用这个想法做，我们先设C=lcm(k,g),那么，只要是C的倍数的V，都是符合答案的，又
设
因为

所以有:
意思是，这要q的取值符合这个范围，那么取相应的V都是符合的，所以答案加上q即可

这个式子可能不太好看，我们化简下:
因为

故,

emmm，推了这么久式子，整个人都快累死了。。。

然后，试试样例。。。emmm，超时了？？？why？？？

冷静分析。。。。

我们发现，若i取1时，i的任意次方都=1，我们永远也算不到i大于n的那天！！

怎么办呢？很简单，我们把1作为底数的情况单独考虑，那么，情况数就是n*n(两指数都从n个数中随便选)，然后我们i从2开始枚举就好了。。。

再来。。。wa了？？？

qwq，怎么回事？

原来，我们枚举i的时候，若我们现在的i可以用一个小于i的数j的k次方表示，即，那么，我们在枚举到j的时候，就已经把现在的情况算了一遍了，所以，我们再算的话就算多了！于是，我们把这种情况的i给剔除掉不算，就行了。。。

然后。。。终于过了qwq。。。

（其实可以先统计底数为1和指数为1的情况，然后i就可以只枚举到了，但个人感觉优化不大(毕竟后面就是O(1)了)）

代码:

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
bool s[1000001];
int main(){
    int n;
    scanf("%d",&n);
    int ans=(1LL*n*n)%mod;//把1作为底的情况先算了
    for(int i=2;i<=n;++i){//枚举公共基底数i
        if(s[i]){
            continue;
        }
        int now=i,maxe=1;//枚举最高指数
        while(now<=n/i){
            ++maxe,now*=i;s[now]=1;
        }
        for(int j=1;j<=maxe;++j){//左边底数为(i^j)
            for(int k=1;k<=maxe;++k){//右边底数为(i^k)
                //求(i^j)^a==(i^k)^b(a,b<=n)的个数
                int C=__gcd(j,k),A=k/C,B=j/C;
                ans=(ans+min((n/A),(n/B)))%mod;//这里把乘化成除更好，不会爆int
            }
        }
    }
    printf("%d",ans);
    return 0;
}