← 返回题目列表

AtCoder · tdpc_eel

P. 鳗鱼

中文机器翻译题面 查看原题

问题陈述

N 有一棵以顶点构成、顶点 a_i 和 按字典顺序比较 b_i 通过边相连的树。这棵树上 K 计算有多少种方法书写不相交的本,结果对 1,000,000,007 取模。
但是,本是指,不同 树上两个顶点之间的路径。如果两条路径不经过公共顶点,则称它们是不相交的。另外,不区分路径的写入顺序(例如,先写入路径 P-Q 再写入路径 R-S,写入路径 S-R 再写入路径 P-Q 视为相同)。

约束

  • 2 ≤ N ≤ 1000
  • 1 ≤ K ≤ 50
  • 1 ≤ a_i, b_i ≤ N
  • 输入将代表一棵树。

输入格式

输入是按以下格式从标准输入给出的。
N K
a_1 b_1
...
a_{N-1} b_{N-1}

输出格式

答案请在一行中输出。

示例输入 1

4 1
1 2
2 3
3 4

示例输出 1

6

示例输入 2

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

示例输出 2

9