给你一棵树 $$$G$$$,有 $$$n$$$ 个顶点和一个整数 $$$k$$$。树的顶点编号从 $$$1$$$ 到 $$$n$$$。
对于顶点 $$$r$$$ 和 $$$G$$$ 的顶点子集 $$$S$$$,使得 $$$|S| = k$$$,我们将 $$$f(r, S)$$$ 定义为当树以 $$$r$$$ 为根时,包含 $$$S$$$ 中所有顶点的最小有根子树的大小。一组顶点 $$$T$$$ 称为有根子树,如果 $$$T$$$ 中的所有顶点都是连接的,并且对于 $$$T$$$ 中的每个顶点,其所有后代都属于 $$$T$$$。
您需要计算顶点 $$$r$$$ 和子集 $$$S$$$ 的所有可能不同组合的 $$$f(r, S)$$$ 之和,其中 $$$|S| = k$$$。正式地,计算以下: $$$$$$\sum_{r \in V} \sum_{S \subseteq V, |S| = k} f(r, S),$$$$$$ 其中 $$$V$$$ 是 $$$G$$$ 中的顶点集。
输出对 $$$10^9 + 7$$$ 取模的答案。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$)。
以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$),表示顶点 $$$x$$$ 和 $$$y$$$ 之间的一条边。
保证给定的边形成一棵树。
输出
打印以 $$$10^9 + 7$$$ 为模的答案。
示例
输入 #1
3 2 1 2 1 3
输出 #1
25
输入 #2
7 2 1 2 2 3 2 4 1 5 4 6 4 7
输出 #2
849
注意
第二个示例中的树如下所示:
在给定的树中,我们有 $$$21$$$ 大小为 $$$2$$$ 的子集。因此,$$$$$$S \in \left\{\{1, 2\}、\{1, 3\}、\{1, 4\}、\{1, 5\}、\{1, 6\}、\{1, 7\}、\{2, 3\}、\{2, 4\}、\{2, 5\}、\{2, 6\}、\{2, 7\}、 \{3, 4\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{4, 5\}, \{4, 6\}, \{4, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\} \right\}.$$$$$$ 由于我们有 $$$7$$$ 个顶点, $$$1 \le r \le 7$$$。我们需要找到所有可能的 $$$r$$$ 和 $$$S$$$ 对的 $$$f(r, S)$$$ 之和。
下面我们列出了 $$$f(r, S)$$$ 对于 $$$r$$$ 和 $$$S$$$ 的某些组合的值。
- $$$r = 1$$$,$$$S = \{3, 7\}$$$。 $$$f(r, S)$$$的值为$$$5$$$,对应的子树为$$$\{2, 3, 4, 6, 7\}$$$。
- $$$r = 1$$$,$$$S = \{5, 4\}$$$。 $$$f(r, S)$$$的值为$$$7$$$,对应的子树为$$$\{1, 2, 3, 4, 5, 6, 7\}$$$。
- $$$r = 1$$$,$$$S = \{4, 6\}$$$。 $$$f(r, S)$$$ 的值为$$$3$$$,对应的子树为$$$\{4, 6, 7\}$$$。