題意

問有多少個滿足以下條件且有 \(n\) 個點 \(m\) 條邊的圖：

1. 沒有自環
2. 每個點的度最大為 \(2\)。
3. 最大的連通塊大小恰好為 \(L\)。

思路

因為要求最大的連通塊恰好為 \(L\)，發現比較惡心。
不妨定義 \(F(L)\) 表示最大為 \(L\) 的，則 \(F(L)-F(L-1)\) 就是答案。
首先分析：由于每個點的度最大為 \(2\)，所以可以判斷每個聯通塊要么是鏈，要么是環。
所以可以設計狀態 \(f_{i,j}\) 表示有 \(i\) 個點，\(j\) 條邊的滿足條件的圖的個數。

• 對于長為 \(i\) 的鏈，有 \(\frac{i!}{2}\) 種方案。
• 對于長為 \(i\) 的環，有 \(\frac{(i-1)!}{2}\) 種方案（原排列）。

除以 \(2\) 是為了去重。
那如何解決連通塊之間的去重問題？可以采用欽定最小值的方法，則我們在 \(n\) 個點里面選 \(i\) 個點出來組成一個連通塊的方案數為 \(\binom{n-1}{i-1}\)，\(-1\) 是因為欽定了最小值。
則有轉移式：

大小為 \(1\) 的鏈和大小為 \(2\) 的環不用除以 \(2\)，因為不重。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const ll N = 305,mod = 1e9+7,inv = 500000004;

int n,m,L;
ll f[N][N];
ll C[N][N],fac[N];

void init() {
	C[0][0]=1,fac[0]=1;
	for(int i=1;i<=300;i++)
		fac[i]=fac[i-1]*i%mod;
	
	for(int i=1;i<=300;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
}

void add(ll &x,ll y){
	(x+=y)%=mod;
}

ll DP(ll lim){
	memset(f,0,sizeof(f));
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int t=1;t<=min(lim,(ll)i);t++){
				if(t>1 && j>=t)add(f[i][j],1ll*f[i-t][j-t]%mod*C[n-i+t-1][t-1]%mod*fac[t-1]%mod*(t==2 ? 1 : inv)%mod);
				if(j>=t-1)add(f[i][j],1ll*f[i-t][j-t+1]%mod*C[n-i+t-1][t-1]%mod*fac[t]%mod*(t==1 ? 1 : inv)%mod);
			}
		}
	}
	return f[n][m];
}
int main() {
	cin>>n>>m>>L;
	init();
	cout<<(DP(L)-DP(L-1)+mod)%mod;
	return 0;
}