代码如下:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
unordered_map <int,int> Cac;
int Pow(int a,int b,int mod) {
	int res = 1;
	a %= mod;
	while (b > 0) {
		if (b & 1) {
			res = res * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
int Phi(int n) {
	if (Cac.count(n)) {
		return Cac[n];
	}
	int res = n;
	for (int p = 2;p * p <= n;++p) {
		if (n % p == 0) {
			while (n % p == 0) {
				n /= p;
			}
			res -= res / p;
		}
	}
	if (n > 1) res -= res / n;
	Cac[n] = res;
	return res;
}
vector <int> Get(int n) {
	vector <int> res;
	for (int d = 1;d * d <= n;++d) {
		if (n % d == 0) {
			res.push_back(d);
			if (d != n / d) {
				res.push_back(n / d);
			}
		}
	}
	return res;
}
int solve(int n) {
	if (n == 1) {
		return 1;
	}
	vector <int> res = Get(n);
	int sum = 0;
	for (int d : res) {
		int phi = Phi(n / d);
		sum = (sum + Pow(n,d,MOD) * phi % MOD) % MOD;
	}
	int ccc = Pow(n,MOD - 2,MOD);
	int ret = sum * ccc % MOD;
	return ret;
}
signed main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		cout << solve(n) << endl;
	} 
	return 0;
}