P - うなぎ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 頂点からなり、頂点 a_i と b_i が辺で結ばれている木がある。この木に K 本の disjoint なパスを書く方法が何通りあるか、mod 1,000,000,007 で求めよ。

ただし、パスとは、異なる 二頂点間の木上での経路のことである。二つのパスは、共通の頂点を通らないとき disjoint であるという。また、パスを書く順番は区別しないものとする (たとえば、パス P-Q を書いた後にパス R-S を書くことも、パス S-R を書いた後にパス P-Q を書くことも同じであるとみなす。)

Constraints

  • 2 ≤ N ≤ 1000
  • 1 ≤ K ≤ 50
  • 1 ≤ a_i, b_i ≤ N
  • The input will represent a tree.

Input Format

入力は以下の形式で標準入力から与えられる。
N K
a_1 b_1
...
a_{N-1} b_{N-1}

Output Format

答えを一行に出力せよ。

Sample Input 1

4 1
1 2
2 3
3 4

Sample Output 1

6

Sample Input 2

8 3
1 2
4 6
6 7
3 2
2 4
4 5
8 6

Sample Output 2

9