$f_{ij}$ 表示加入 $i$ 条边, $j$ 个点的度数是奇数的方案数,然后暴力

#include
     
      using namespace std;#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)#define For(i,a,b) for(int i=(a),i##_end=(b);i
      
       =i##_st;--i)#define fi first#define se second#define pb push_back#define mp make_pair#define dbg(x) cerr<<#x" = "<
       
        <
        
         nxt)typedef long long ll;typedef pair
         
           pii;const int inf=~0u>>1,mod=10007;inline int rd() {    int x,c,f=1;while(!isdigit(c=getchar()))f=c!='-';x=c-'0';    while(isdigit(c=getchar()))x=x*10+c-'0';return f?x:-x;}const int N=1011;char d[N];int f[N][N],inv[N];inline int C(int i){return i<2?0:i*(i-1)/2%mod;}int main(){#ifdef flukehn	freopen("test.txt","r",stdin);#endif	inv[1]=1;	For(i,2,N)inv[i]=(mod-mod/i)*inv[mod%i]%mod;	int n=rd(),m=rd(),K=rd();	rep(i,1,m){		d[rd()]^=1;		d[rd()]^=1;	}	int p=0;	rep(i,1,n)p+=d[i];	f[0][p]=1;	rep(i,1,K)rep(j,0,n){		f[i][j]=inv[i]*((ll)f[i-1][j]*j*(n-j)%mod+(ll)(j+2<=n?f[i-1][j+2]:0)*C(j+2)%mod+(ll)(j>=2?f[i-1][j-2]:0)*C(n-j+2)%mod-(i>=2?f[i-2][j]:0)*(C(n)-i+2)%mod)%mod;	}	int r=f[K][0];	if(r<0)r+=mod;	cout<
          
           <