记录编号	271211	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的欧拉图	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	3.633 s
提交时间	2016-06-15 19:14:53	内存使用	12.29 MiB

#define maxn 131072ul

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <algorithm>

const int mod=1e9+7,M=32000;

int power(int p,long long k){
	int ret=1;
	while(k){
		if(k&1) ret=1ll*ret*p%mod;
		k>>=1ll,p=1ll*p*p%mod;
	} return ret;
}

namespace FFT{

	using namespace std;

	typedef long long ll;
	typedef long double ld;

	struct cpx{
		ld r,i;
		cpx(ld _r=0,ld _i=0){r=_r,i=_i;}
		cpx operator + (const cpx &x){return cpx(r+x.r,i+x.i);}
		cpx operator - (const cpx &x){return cpx(r-x.r,i-x.i);}
		cpx operator * (const cpx &x){return cpx(r*x.r-i*x.i,r*x.i+i*x.r);}
		cpx conj(){return cpx(r,-i);}
	}A[maxn],B[maxn];

	const ld pi=acos(-1.0);

	int N,a0[maxn],b0[maxn],a1[maxn],b1[maxn];

	void setlen(int len){
		N=1;
		for(;N<len;N<<=1);
		N<<=1; return;
	}

	void fft(cpx *f,int n,int flag){
		for(register int i=0,j=0;i<n;i++){
			if(i>j) std::swap(f[i],f[j]);
			for(int t=n>>1;(j^=t)<t;t>>=1);
		} register cpx wn,w,u,t;
		for(register int m=2,i,p,k;m<=n;m<<=1){
			w=cpx(1,0),wn=cpx(cos(2.0*pi/m),flag*sin(2.0*pi/m));
			for(i=0,p=m>>1;i<n;i+=m,w=cpx(1,0)) for(k=0;k<p;k++,w=w*wn)
				u=f[i+k],t=w*f[i+k+p],f[i+k]=u+t,f[i+k+p]=u-t;
		}
		if(flag==-1) for(register int i=0;i<n;i++) f[i].r/=n; return;
	}

	void mul(int *a,int *b,int *c){
		for(int i=0;i<N;i++) A[i]=cpx(a[i],b[i]);
		fft(A,N,1);
		for(int i=0,j;i<N;i++){
			j=(N-i)&(N-1);
			B[i]=(A[i]*A[i]-(A[j]*A[j]).conj())*cpx(0,-0.25);
		} fft(B,N,-1);
		for(int i=0;i<N;i++) c[i]=((long long)(B[i].r+0.5))%mod;
		return;
	}

	void mul_mod(int *a,int *b,int *c){
		for(int i=0;i<N;i++) c[i]=0;
		if(N<=128){
			for(int i=0;i<N;i++) for(int j=0;j<=i;j++){
				(c[i]+=1ll*a[j]*b[i-j]%mod)%=mod;
			} return;
		}
		for(int i=0;i<N;i++) a0[i]=a[i]/M,b0[i]=b[i]/M; mul(a0,b0,a0);
		for(int i=0;i<N;i++) c[i]=1ll*a0[i]*M*M%mod,a1[i]=a[i]%M,b1[i]=b[i]%M; mul(a1,b1,a1);
		for(int i=0;i<N;i++) c[i]=(a1[i]+c[i])%mod,a0[i]=(a0[i]+a1[i])%mod,a1[i]=a[i]/M+a[i]%M,b1[i]=b[i]/M+b[i]%M;	 mul(a1,b1,a1);
		for(int i=0;i<N;i++) c[i]=(1ll*M*(a1[i]-a0[i]+mod)%mod+c[i])%mod; return;
	}
};

int tmp[maxn],result[maxn],F[maxn],G[maxn],H[maxn],inv[maxn],invf[maxn];

void getInv(int *f,int *g,int n){
	static int tmp[maxn];
	if(n==1){ g[0]=power(f[0],mod-2); return; }
	getInv(f,g,n>>1); memcpy(tmp,f,sizeof(int)*n);
	memset(tmp+n,0,sizeof(int)*n); FFT::setlen(n);
	FFT::mul_mod(g,tmp,result);
	for(int i=0;i<n;i++) result[i]=(mod-result[i])%mod; (result[0]+=2)%=mod;
	memset(result+n,0,sizeof(int)*n);
	FFT::mul_mod(g,result,tmp);
	for(int i=0;i<n;i++) g[i]=tmp[i];
	memset(g+n,0,sizeof(int)*n); return;
}

int main(){
	freopen("Crazy_Graph.in","r",stdin);
    freopen("Crazy_Graph.out","w",stdout);
	int n; scanf("%d",&n);
	int N=1; for(;N<=n;N<<=1);
	inv[0]=inv[1]=invf[0]=1;
	for(register int i=2;i<N;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(register int i=1;i<N;i++) invf[i]=1ll*invf[i-1]*inv[i]%mod;
	for(register int i=1,gn;i<N;i++){
		gn=power(2,1ll*(i-1)*(i-2)/2ll);
		H[i]=1ll*gn*invf[i-1]%mod,G[i]=1ll*gn*invf[i]%mod;
	}
	G[0]=1,getInv(G,F,N); FFT::setlen(n),FFT::mul_mod(F,H,result);
	int rp=(1+1ll*n*(n-1)/2ll)%mod;
	printf("%d\n",1ll*result[n]*power(invf[n-1],mod-2)%mod*rp%mod);
	return 0;
}