记录编号	419971	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的欧拉图	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.402 s
提交时间	2017-07-03 17:41:44	内存使用	9.81 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1<<17|1,p=1e9+7;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
int n,f[N],g[N];
struct poly{
	int a[N],b[N],w[N],iw[N],p,gen;
	void init(int P,int GEN){p=P;gen=GEN;}
	int inc(int x,int y){x+=y;return x>=p?x-p:x;}
	int dec(int x,int y){x-=y;return x<0?x+p:x;}
	int mul(int x,int y){return (ll)x*y%p;}
	int power(int x,int y){
		int ans=1;
		for (;y;y>>=1,x=mul(x,x))
			if (y&1) ans=mul(ans,x);
		return ans;
	}
	void init(int n){
		w[0]=1;w[1]=power(gen,(p-1)/n);
		for (int i=2;i<=n;i++) w[i]=mul(w[i-1],w[1]);
		for (int i=0;i<=n;i++) iw[i]=w[n-i];
	}
	void fft(int n,int *a,int *w){
		for (int i=0,j=0;i<n;i++){
			if (i<j) swap(a[i],a[j]);
			for (int k=n>>1;(j^=k)<k;k>>=1);
		}
		for (int i=2;i<=n;i<<=1){
			int m=i>>1,step=n/i;
			for (int j=0;j<n;j+=i)
			for (int k=0,pos=0;k<m;k++,pos+=step){
				int t=mul(a[j+k+m],w[pos]);
				a[j+k+m]=dec(a[j+k],t);
				a[j+k]=inc(a[j+k],t);
			}
		}
		if (w==iw){
			int del=power(n,p-2);
			for (int i=0;i<n;i++) a[i]=mul(a[i],del);
		}
	}
	void multify(int size){
		init(size);
		fft(size,a,w);fft(size,b,w);
		for (int i=0;i<size;i++) a[i]=mul(a[i],b[i]);
		fft(size,a,iw);
	}
}A,B,C;
int CRT(int a1,int a2,int a3){
	static int AiB=B.power(A.p,B.p-2),BiA=A.power(B.p,A.p-2);
	static ll AB=(ll)A.p*B.p,ABiC=C.power(AB%C.p,C.p-2);
	ll a=((ll)A.mul(BiA,a1)*B.p+(ll)B.mul(AiB,a2)*A.p)%AB;
	return (a+((a3-a)%C.p+C.p)%C.p*ABiC%C.p*(AB%p)%p)%p;
}
int a[N],b[N];
void multify(int size){//将a*b存到a里面 
	for (int i=0;i<size;i++){
		A.a[i]=a[i]%A.p;
		B.a[i]=a[i]%B.p;
		C.a[i]=a[i]%C.p;
		A.b[i]=b[i]%A.p;
		B.b[i]=b[i]%B.p;
		C.b[i]=b[i]%C.p;
	}
	A.multify(size);
	B.multify(size);
	C.multify(size);
	for (int i=0;i<size;i++) a[i]=CRT(A.a[i],B.a[i],C.a[i]);
}
void getinv(int n,int *a,int *b){
	if (n==1) return void(b[0]=power(a[0],p-2));
	getinv((n+1)>>1,a,b);
	int size=1;
	while (size<n+n) size<<=1;
	for (int i=0;i<n;i++) ::a[i]=dec(0,a[i]);
	for (int i=n;i<size;i++) ::a[i]=0;
	for (int i=0;i<size;i++) ::b[i]=b[i];
	multify(size);
	::a[0]=inc(::a[0],2);
	multify(size);
	for (int i=0;i<n;i++) b[i]=::a[i];
	for (int i=n;i<size;i++) b[i]=0;
}
int inverse[N],jc[N],JC[N];
int main()
{
	freopen("Crazy_Graph.in","r",stdin);
	freopen("Crazy_Graph.out","w",stdout);
	A.init(119<<23|1,3);
	B.init(479<<21|1,3);
	C.init(1917<<19|1,5);
	scanf("%d",&n);n++;
	inverse[1]=1;
	for (int i=2;i<=n;i++) inverse[i]=mul(p-p/i,inverse[p%i]); 
	jc[0]=JC[0]=1;
	for (int i=1;i<=n;i++){
		jc[i]=mul(jc[i-1],i);
		JC[i]=mul(JC[i-1],inverse[i]);
	}
	f[0]=f[1]=f[2]=1;
	for (int i=3;i<n;i++) f[i]=power(2,(ll)(i-1)*(i-2)/2%(p-1));
	for (int i=0;i<n;i++) f[i]=mul(f[i],JC[i]);
	getinv(n,f,g);
	int size=1;
	while (size<n+n) size<<=1;
	for (int i=0;i<size;i++) a[i]=b[i]=0;
	for (int i=0;i<n;i++) a[i]=g[i];
	for (int i=0;i<n;i++) b[i]=mul(f[i],i);
	multify(size);
	g[0]=0;
	for (int i=1;i<n;i++) g[i]=mul(a[i],jc[i-1]);
	for (int i=n;i<size;i++) g[i]=0;
	printf("%lld\n",((ll)(n-1)*(n-2)/2%p+1)*g[n-1]%p);
	return 0;
}