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

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cctype>
#include<ctime>
#include<cmath>
#include<queue>
#include<list>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
#define INF 0x7fffffff
#define F(i,l,r) for(int i=l;i<=r;i++)
#define D(i,r,l) for(int i=r;i>=l;i--)
#define rep(i,n) for(i=1;i<=n;i++)
const int maxn=5000100;
const int mod=100000007;
bool zs[maxn];
int n;
void mk()
{
	scanf("%d",&n);
	int i,j;
	for(i=2;i<=n/2+1;i++)
	{
		if(!zs[i])
		{
			for(j=2; i*j <=n;j++)
			zs[i*j]=1;
		}
	}
}
ll qh(ll v)
{
	ll ans=0;
	ll x=n;
	for(;x;x/=v,ans+=x);
	return ans;
}
ll ksm(int a,ll b)
{
	ll ans=1,x=a%mod;
	for(;b;b/=2,x=(x*x)%mod)
	if(b&1)
		ans=(ans*x)%mod;
 
	return ans;
}
void solve()
{
	ll j,sum,ans=1;
	int i;
	for(i=2;i<=n/2+1;i++)
	{
		if(!zs[i])
		{
			j=0;
			sum=qh(i);
			if(sum&1) sum--;
			if(sum!=0)
			j=ksm(i,sum);
			if(j!=0)
			ans=(ans*j)%mod;
		}
	} 
	printf("%I64d\n",ans);
}
int Main(){
	freopen("xnumber.in","r",stdin);
	freopen("xnumber.out","w",stdout);
	mk();
	solve();
}
int start=Main();
int main(){;}