记录编号	337394	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	__完全平方数	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	4.292 s
提交时间	2016-11-04 13:09:58	内存使用	77.31 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=5000010;
const int Mod=100000007;
bool check[N];
int prime[N],cnt;
int nxt[N],id[N];
void Solve(int n){
  for(int i=2;i<=n;i++){
    if(!check[i]){
      prime[++cnt]=i;
      id[i]=cnt;
      nxt[i]=1;
    }
    for(int j=1;j<=cnt;j++){
      if(i*prime[j]>n)break;
      check[i*prime[j]]=true;
      nxt[i*prime[j]]=i;
      if(i%prime[j]==0)break;
    }
  }
}
int c[N];

int Quick_pow(int x,int k){
  int ret=1;
  while(k){
    if(k&1)
      ret=1ll*ret*x%Mod; 
    x=1ll*x*x%Mod;k>>=1;
  }
  return ret;
}

int n;
int ans=1;
int main(){
  freopen("xnumber.in","r",stdin);
  freopen("xnumber.out","w",stdout);
  scanf("%d",&n);Solve(n);
  for(register int i=2,x;i<=n;i++){
    x=i;
    while(x!=1){
      c[id[x/nxt[x]]]+=1;
      x=nxt[x];
    }
  }
  for(int i=1;i<=cnt;i++){
    if(c[i]&1)c[i]-=1;
    ans=(1ll*ans*Quick_pow(prime[i],c[i]))%Mod;
  }
  printf("%d\n",ans);
  return 0;
}