题意：

求有多少方案使得 a,b,c,d 满足 a^b=c^d， 1\leq a,b,c,d \leq n，结果对 10^9+7 取模

分析：

可以将 a,c 的取值分为以下三种情况：

• a=c=1 ,很显然此时 b,d 可以取 [1,n] 内的任意值，故方案数为 n^2
• a=c\neq 1,此时 b,d 取值必须相等，故方案数为 n*(n-1)
• a \neq c, 我们从2到 \sqrt{n} 枚举a，求出满足 a^b=c^d 的 abcd，对于每个a要遍历b,d，计算出来的方案要乘以2，因为ac位置可以调换，每次遍历是log级别的，然后再将a的次方全部打上记号，后面枚举到就无需计算了。为什么a只需要枚举到 \sqrt{n} ？因为当 a > \sqrt{n}，c不可能大于a了，a=c的情况在第二种情况已经计算过，a>c的情况在前面枚举a时计算过了。

最后，再将三种情况算得方案数相加。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
ll qpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res *= a;
		a *= a;
		b >>= 1;
	}
	return res;
}
ll n;
ll range;
int f[100010];
ll gcd(ll x, ll y) {
	return y == 0 ? x : gcd(y, x % y);
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
void solve() {
	cin >> n;
	range = sqrt(n);
	ll ans = 0;
	for (ll i = 2; i <= range; i++) {
		if (f[i] == 0) {
			for (ll j = 1; 1; j++) {
				ll tmp = qpow(i, j);
				if (tmp <= range) {
					f[tmp] = 1;
				}
				if (tmp > n) break;
				for (ll k = 1; k < j; k++) {
					ans += n / (lcm(j, k) / min(j, k)) * 2;
					ans %= mod;
				}
			}
		}
	}

	cout << (ans + (n - 1) * n % mod + n * n % mod) % mod << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
	}
	return 0;
}