记录编号	252531	评测结果	AAAAAAAAAA
题目名称	最小生成树	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-04-20 16:31:28	内存使用	0.51 MiB

#include<cstdio>
#include<iostream>
using namespace std;
const int SIZEN=20010;
typedef long long LL;
int N;
LL phi[SIZEN];
const LL MOD=100000007;
bool co[SIZEN]={0};
int Prime[SIZEN],cnt=0;
void prime()
{
	phi[1]=1;
	for(int i=2;i<=N;i++)
	{
		//cout<<i<<endl;
		if(!co[i]) Prime[cnt++]=i,phi[i]=i-1;
		for(int j=0;j<cnt&&Prime[j]*i<=N;j++)
		{
			co[i*Prime[j]]=1;
			if(i%Prime[j]==0)
			{
				phi[i*Prime[j]]=Prime[j]*phi[i];
				break;
			}
			phi[i*Prime[j]]=(Prime[j]-1)*phi[i];
		}
	}
}
int main()
{
	freopen("msta.in","r",stdin);
	freopen("msta.out","w",stdout);
	scanf("%d",&N);
	//cout<<N<<endl;
	prime();
	LL ans=1;
	for(int i=2;i<=N;i++)
	{
		//cout<<phi[i]<<endl;
		ans*=phi[i];
		ans%=MOD;
	}
	printf("%lld\n",ans);
	return 0;
}