← 返回题目列表

Codeforces · 1097/G

G. 弗拉迪斯拉夫和伟大的传奇

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

这里曾经有一个伟大的传奇,但一些巨魔入侵了 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$$$