题目描述

给定一个 $n$ 个节点的树。现在你拥有 $k$ 种颜色，你要用这些颜色给树上的每个节点染色，使得任何两个距离不大于 $2$ 的不同节点所被染的颜色不同。

由于答案可能过大，请将其对 $10^9+7$ 取模。

输入格式

第一行两个整数 $n, k$。接下来 $n - 1$ 行，每行两个整数 $a_i, b_i$，表示 $a_i$ 与 $b_i$ 之间有一条边。

$1 \le n, k \le 10^5$，$1 \le a_i, b_i \le N$。

输出格式

输出不同的染色方法数对 $10^9+7$ 取模的结果。

4 3
1 2
2 3
3 4

6

5 4
1 2
1 3
1 4
4 5

48

16 22
12 1
3 1
4 16
7 12
6 2
2 15
5 16
14 16
10 11
3 10
3 13
8 6
16 8
9 12
4 3

271414432