记录编号	252479	评测结果	AAAAAAAAAA
题目名称	最小生成树	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2016-04-20 15:58:01	内存使用	0.39 MiB

//KZNS
#include <fstream>
using namespace std;
//
ifstream fin ("msta.in");
ofstream fout ("msta.out");
const int Nmax = 20006;
//
int phi[Nmax];
int N;
long long ed = 1;
//
int main() {
	fin >> N;
	phi[1] = 1;
	for (int i = 2; i <= N; i++) {
		if (!phi[i]) {
			phi[i] = i-1;
			for (int j = i+i; j <= N; j+=i) {
				if (!phi[j])
					phi[j] = j;
				phi[j] = phi[j]*(i-1)/i;
			}
		}
		ed *= phi[i];
		ed %= 100000007;
	}
	fout << ed;
	return 0;
}
//UBWH