这里曾经有一个伟大的传奇,但一些巨魔入侵了 Codeforces 并抹去了它。对我们来说太糟糕了,但在巨魔社会中,他赢得了终极巨魔的称号。至少对于他们来说,这是一件好事。也许正式声明对我们来说会更好?
给定一棵树 $$$T$$$,其顶点编号为 $$$n$$$,编号从 $$$1$$$ 到 $$$n$$$。对于 $$$T$$$ 的顶点的每个非空子集 $$$X$$$,令 $$$f(X)$$$ 为 $$$T$$$ 的最小连通子树中的最小边数,该子树包含来自 $$$X$$$ 的每个顶点。
您还获得了一个整数 $$$k$$$。您需要计算所有非空顶点子集 $$$(f(X))^k$$$ 的总和,即:
$$$$$$ \sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} (f(X))^k。 $$$$$$
由于结果可能非常大,因此输出它对 $$$10^9 + 7$$$ 取模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq k \leq 200$$$) — 树的大小和上面总和中的指数。
以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i,b_i \leq n$$$) — 由相应边连接的顶点的索引。
保证边形成一棵树。
输出
打印一个整数 - 请求的总和模 $$$10^9 + 7$$$。
示例
输入 #1
4 1 1 2 2 3 2 4
输出 #1
21
输入 #2
4 2 1 2 2 3 2 4
输出 #2
45
输入 #3
5 3 1 2 2 3 3 4 4 5
输出 #3
780
注意
在前两个示例中,$$$f$$$ 的值如下:
$$$f(\{1\}) = 0$$$
$$$f(\{2\}) = 0$$$
$$$f(\{1, 2\}) = 1$$$
$$$f(\{3\}) = 0$$$
$$$f(\{1, 3\}) = 2$$$
$$$f(\{2, 3\}) = 1$$$
$$$f(\{1, 2, 3\}) = 2$$$
$$$f(\{4\}) = 0$$$
$$$f(\{1, 4\}) = 2$$$
$$$f(\{2, 4\}) = 1$$$
$$$f(\{1, 2, 4\}) = 2$$$
$$$f(\{3, 4\}) = 2$$$
$$$f(\{1, 3, 4\}) = 3$$$
$$$f(\{2, 3, 4\}) = 2$$$
$$$f(\{1, 2, 3, 4\}) = 3$$$