记录编号	367668	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	__完全平方数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.202 s
提交时间	2017-02-01 11:05:23	内存使用	21.72 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e6+10,mod=100000007;
int n,p[N],cnt;bool isp[N];
ll mi(ll x,ll y){
	ll ans=1;
	for (;y;y>>=1,x=x*x%mod)
		if (y&1) ans=ans*x%mod;
	return ans;
}
int main()
{
	freopen("xnumber.in","r",stdin);
	freopen("xnumber.out","w",stdout);
	scanf("%d",&n);
	ll ans=1;
	for (int i=2;i<=n;i++){
		if (!isp[i]){
			p[++cnt]=i;
			int Mi=0;
			for (int x=n/i;x;x/=i) Mi+=x;
			if (Mi&1) Mi--;
			ans=ans*mi(i,Mi)%mod;
		}
		for (int j=1;j<=cnt&&i*p[j]<=n;j++){
			isp[i*p[j]]=1;
			if (!(i%p[j])) break;
		}
	}
	printf("%lld\n",ans);
	return 0;
}