记录编号	612113	评测结果	AAAAAAAAAA
题目名称	4304.数图	最终得分	100
用户昵称	2_16鸡扒拌面	是否通过	通过
代码语言	C++	运行时间	3.895 s
提交时间	2026-02-10 14:49:08	内存使用	8.35 MiB

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1000+10;
int n,MOD=1e9+7,frac[MAXN],dp[MAXN][MAXN],f[MAXN][MAXN],C[MAXN][MAXN],p2[MAXN],i2[MAXN];
signed main() {
    freopen("grafy.in","r",stdin);
    freopen("grafy.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	p2[0]=1; ffor(i,1,n) p2[i]=p2[i-1]*2%MOD;
	i2[0]=1; ffor(i,1,n) i2[i]=i2[i-1]*(MOD+1)/2%MOD;
	frac[0]=1; ffor(i,1,n+n) frac[i]=frac[i-1]*i%MOD;
	ffor(i,0,n) {
		C[i][0]=1;
		ffor(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;	
	}
	ffor(i,0,n) ffor(j,0,i) {
		if(j==0) {f[i][j]=1; continue ;}
		f[i][j]=(i-j)*f[i-1][j-1]%MOD;
		if(j-1) f[i][j]=(f[i][j]+(j-1)*(f[i-2][j-2]+f[i-1][j-1]))%MOD;
	}
	ffor(i,0,n+n) ffor(j,0,i) {
		if(j==0) {dp[i][j]=frac[i];continue ;}
		dp[i][j]=(i-j)*dp[i-1][j-1]%MOD;
		if(j-1) dp[i][j]=(dp[i][j]+(j-1)*(dp[i-2][j-2]+dp[i-1][j-1]))%MOD;
	}
	int ans=0;
	ffor(c,0,n) ffor(a,c,n) ffor(b,c,n+c-a) {
		int mul=C[n][c]*C[n-c][a-c]%MOD*C[n-a][b-c]%MOD;
		if((a+b-c)&1) mul=-mul;
		ans=(ans+mul*p2[b-c]%MOD*f[n-b][a-c]%MOD*dp[2*(n-a-b+c)+b-c][b-c]%MOD*i2[n-a-b+c])%MOD;
	}
	
	    ans=ans*i2[n]%MOD;
	    cout<<(ans%MOD+MOD)%MOD;
	return 0;
}