记录编号	253026	评测结果	AAAAAAAAAA
题目名称	最小生成树	最终得分	100
用户昵称	FETS 1/3	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2016-04-21 15:29:17	内存使用	0.66 MiB

#include<cstring>
#include<iostream>
#include<cstdio>
#include<ctime>
using namespace std;
#define N 30000
int vis[N];
int p[N],cnt,phi[N];
const int MOD=100000007;
int Euler(int n)
{
	phi[1]=1;
	for (int i=2;i<n;i++)
	{
		if (!vis[i])
		{
			p[cnt++]=i;
			phi[i]=i-1;
		}
		for(int j=0;j<cnt&&i*p[j]<n;++j)
		{
			vis[i*p[j]]=1;
			if (i%p[j]) 
				phi[i*p[j]]=phi[i]*phi[p[j]];
			else 
			{
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
		}
	}
	return cnt;
}
 
int main()
{
	freopen("msta.in","r",stdin);
	freopen("msta.out","w",stdout);
	int n;
	scanf("%d",&n);
	Euler(N);
	long long ans=1;
	for(int i=1;i<=n;i++)
	{
		ans=1LL*ans*phi[i]%MOD;
	}
	printf("%d",ans);
	return 0;
}