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

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