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

/*=========================================*
  * Auther: Riolu
  * Time: 2016.11.4
  * ©Copyright 2016 Riolu. All Rights Reserved.
  *=========================================*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;

typedef long long ll;
const int N =5000001,M=1e8 +7;
bool pri[N];
ll n,ans=1;

ll ask(ll x){
	ll t=0,i;
	for(i=n/x;i>0;i/=x)t+=i;
	return t;
}

ll qpow(ll a,ll b){
	ll t=1,x=a%M;
	for(;b>0;b>>=1,x=(x*x)%M)
		if(b%2) t=(t*x)%M;
	return t;
}

int main(){
	freopen("xnumber.in","r",stdin);
	freopen("xnumber.out","w",stdout);

	ll i,j,sum,l;
	cin>>n;l=(n>>1)+1;
	for(i=2;i<=l;i++) if(!pri[i])
		for(j=i<<1;j<=n;j+=i)pri[j]=1;
	for(i=2;i<=l;i++) if(!pri[i]){
		j=0;
		sum=ask(i); 
		if(sum%2) sum--;
		if(sum!=0) j=qpow(i,sum);
		if(j!=0) ans=(ans*j)%M;
	}
	cout<<ans<<endl;
	return 0;
}
/*

*/