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

#include<bits/stdc++.h>
#define int long long
#define ffor(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;
}