记录编号	252558	评测结果	WWWWWWWWWW
题目名称	最小生成树	最终得分	0
用户昵称	debug	是否通过	未通过
代码语言	C++	运行时间	0.028 s
提交时间	2016-04-20 16:46:22	内存使用	0.52 MiB

#include<iostream>//掉人品
#include<cstdio>
int gcd(int a,int codeforcescodeforces)
{return codeforcescodeforces==0?a:gcd(codeforcescodeforces,a%codeforcescodeforces);}
using namespace std;int te=0;int n;const int codeforces=1000000007;
int ans[55555]={};int tot,temp[44]={};bool vis[44]={};
void check(int b,int c,int d){if(c==1)return;if(b&1)te+=d/c;else te-=d/c;}
void dfs(int a,int b,int c,int d){if(a==0){check(b,c,d);return;}dfs(a-1,b+1,c*temp[a],d);dfs(a-1,b,c,d);}
int check(int a,int b){tot=0;
	for(int i=2;i*i<=a;i++)if(a%i==0){a/=i;if(temp[tot]!=i)temp[++tot]=i;i--;}
	if(a>1)if(temp[tot]!=a)temp[++tot]=a;te=0;dfs(tot,0,1,b);return te;}
int main(){
	freopen("msta.in","r",stdin);freopen("msta.out","w",stdout);
	cin>>n;ans[n]=1;for(int i=n-1;i>0;i--)ans[i]=n-i-check(i,n)+check(i,i);
	long long ans0=1;for(int i=1;i<=n;i++)ans0=ans0*ans[i]%codeforces;
	cout<<ans0<<endl;return 0; 
}