F - Unbranched Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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

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

制約

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

入力

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

N M L

出力

答えを出力せよ。

入力例 1

3 2 3

出力例 1

3

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

  • 1-2 間と 2-3 間に辺がある。
  • 1-2 間と 1-3 間に辺がある。
  • 1-3 間と 2-3 間に辺がある。

入力例 2

4 3 2

出力例 2

6

入力例 3

300 290 140

出力例 3

211917445

Score : 600 points

Problem Statement

Find the number of graphs with N labeled vertices and M unlabeled edges, not necessarily simple or connected, that satisfy the following conditions, modulo (10^9+7):

  • There is no self-loop;
  • The degree of every vertex is at most 2;
  • The maximum of the sizes of the connected components is exactly L.

Constraints

  • 2 \leq N \leq 300
  • 1\leq M \leq N
  • 1 \leq L \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M L

Output

Print the answer.

Sample Input 1

3 2 3

Sample Output 1

3

When the vertices are labeled 1 through N, the following three graphs satisfy the condition:

  • The graph with edges 1-2 and 2-3;
  • The graph with edges 1-2 and 1-3;
  • The graph with edges 1-3 and 2-3.

Sample Input 2

4 3 2

Sample Output 2

6

Sample Input 3

300 290 140

Sample Output 3

211917445