题目描述

頂点にラベルが付き辺にはラベルが付いていない $N$ 頂点 $M$ 辺の単純とも連結とも限らないグラフであって、以下の条件を満たすものの個数を $10^9+7$ で割ったあまりを求めてください。

• 自己ループを持たない
• すべての頂点の次数が $2$ 以下である
• 各連結成分のサイズを並べたとき、その最大値がちょうど $L$ である

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $L$

输出格式

答えを出力せよ。

题目大意

求 $N$ 个点，$M$ 条边且满足以下条件的图的数量：

• 图中无自环；

• 每个点度数最多为 $2$；

• 连通块大小的最大值恰好为 $L$。

答案对 $10^9+7$ 取模。

$2\le N\le300$，$1\le M,L\le N$。

3 2 3

3

4 3 2

6

300 290 140

211917445

提示

制約

• $2\ \leq\ N\ \leq\ 300$
• $1\leq\ M\ \leq\ N$
• $1\ \leq\ L\ \leq\ N$
• 入力はすべて整数

Sample Explanation 1

頂点に $1$ から $N$ の番号を付けたとき、以下の $3$ 通りのグラフが条件を満たします。 - $1-2$ 間と $2-3$ 間に辺がある。 - $1-2$ 間と $1-3$ 間に辺がある。 - $1-3$ 間と $2-3$ 間に辺がある。