记录编号	337954	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	__完全平方数	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.865 s
提交时间	2016-11-04 23:26:38	内存使用	1.77 MiB

#include<cstdio>
#include<cstring>
#define file(x) "xnumber."#x
typedef long long ll;
const int N=5000010;
const ll M=100000007;
int n,pt[N/10],sz,cnt[N/10];
bool p[N];
ll ans=1;
ll qpow(ll a,ll r){
	ll s=1;
	a%=M;
	while(r){
		if(r&1) s=s*a%M;
		a=a*a%M,r>>=1;
	}
	return s;
}
int Main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	memset(p,1,sizeof(p));
	scanf("%d",&n);
	for(int i=2;i<=n;i++) if(p[i]){
		int x=n,cnt=0;
		do{
			x/=i;
			cnt+=x;
		}while(x);
		ans=ans*qpow(i,cnt%2?cnt-1:cnt)%M;
		for(int j=i+i;j<=n;j+=i) p[j]=0;
	}
	printf("%lld",ans);
}
int enter=Main();
int main(){
}