#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
bool isPrime(long long n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (long long i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}
long long solve(long long n)
{
    long long cnt=0;
    for (long long i = 2; i < n; i++)
    {
        if (isPrime(i))
            cnt++;
    }
    return cnt;
}
long long  phi(long long n)
{
    long long res = n;
    for (long long i = 2; i * i < n; ++i)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
            {
                n /= i;
            }
            res -= res / i;
        }
    }
    if (n != 1)
    {
        res -= res / n;
    }
    return res;
}

long long largestPower(long long n, long long p)
{
	long long x = 0;
	while (n) {
		n /= p;
		x += n;
	}
	return x;
}
long long  power(long long  x, long long y)
{
	long long res = 1;
	x = x % mod;
	while (y > 0) {
		if (y & 1)
			res = (res * x) % mod;
		y = y >> 1;
		x = (x * x) % mod;
	}
	return res;
}

long long modFact(long long n)
{
	if (n >= mod)
		return 0;
	long long res = 1;
	bool isPrime[n + 1];
	memset(isPrime, 1, sizeof(isPrime));
	for (long long i = 2; i * i <= n; i++) {
		if (isPrime[i]) {
			for (long long j = 2 * i; j <= n; j += i)
				isPrime[j] = 0;
		}
	}
	for (long long i = 2; i <= n; i++) {
		if (isPrime[i]) {
			long long k = largestPower(n, i);

			res = (res * power(i, k)) % mod;
		}
	}
	return res;
}
int main()
{
    long long t;
    cin>>t;
    while(t--)
    {
        long long n;
        cin>>n;
        long long h = phi(n);
        long long kk = solve(n);
        long long pp = modFact(kk);
        cout<<power(h,pp)<<endl;
    }
}