#include<bits/stdc++.h>
using namespace std;
bool a[10000000]={0};
long long b[1700000];
long long c[1700000];
void sieve() {
long long int i,j;
long long int l=(long long int)sqrt(10000000);
for(i=2;i<=l;i+=1)
{
if(a[i]==1)
continue;
for(j=2*i;j<=10000000;) {
a[j]=1;
j=j+i;
}
}
long long int k=0,count=1;
for(i=2;i<=10000000;i++)
{
if(a[i]==0)
k++;
if(i%6==0)
b[count++]=k;
}
}
long long int fi(long long int n)
{
long long int i,result = n;
for(i=2;i*i <= n;i++)
{
if (n % i == 0) result -= result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result -= result / n;
return result;
}
long long fact(long long n,long long mod) {
long long ans=1;
while(n>1) {
ans=(ans*n)%mod;
n--;
}
return ans;
}
long long pow_modulo(long long base,long long p,long long mod) {
long long ans;
ans=1;
while(p!=0)
{
if(p%2!=0)
ans=(base*ans)%mod;
base=(base*base)%mod;
p=p/2;
}
return ans;
}
int main() {
sieve();
long long t,n,mod,ans,ans1,ans2,ans3,p;
mod=10e9+7;
scanf("%lld",&t);
while(t--) {
scanf("%lld",&n);
if(n%6!=0) {
ans=1;
}
else {
ans1=fi(n);
n=n/6;
ans2=b[n];
// printf("%lld %lld\n",ans1,ans2);
if(ans2<=ans1)
ans=1;
else {
ans3=ans2-ans1;
p=fact(ans3,mod);
/// printf("ans1=%lld p=%lld\n",ans1,p);
ans=pow_modulo(ans1,p,mod);
}
}
printf("%lld\n",ans);
}
return 0;
}
Plz check my code why i am getting wa..
