C - Not Too Close

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800

問題文

N 頂点の無向グラフであって、以下の条件をすべて満たすものの個数を 10^9 + 7 で割った余りを求めてください。

  • N 個の頂点には 1 から N までの番号が振られている。
  • グラフは自己辺や多重辺を持たない(連結である必要はない)。
  • すべての辺の長さを 1 とすると、頂点 1, 2 間の最短距離は D である。

注記

二つのグラフ G_1, G_2 は、以下が満たされる場合に異なるとみなされ、満たされない場合に同一とみなされます。

  • ある整数の組 (i, j) (1 ≤ i < j ≤ N) が存在し、頂点 i, j を直接結ぶ辺が G_1, G_2 のうち一方のみに存在する。

制約

  • 1 ≤ D < N ≤ 30
  • N, D は整数である。

入力

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

N D

出力

条件をすべて満たすグラフの個数を 10^9 + 7 で割った余りを出力せよ。


入力例 1

4 3

出力例 1

2

条件を満たすグラフは下図の 2 通りです。


入力例 2

4 2

出力例 2

14

条件を満たすグラフは下図の 14 通りです。


入力例 3

30 15

出力例 3

313862829

mod (10^9 + 7) にご注意ください。