### 问题描述 诺伊拥有一片神奇的森林，森林由 $N$ 个神奇的树木节点组成，每个节点都可以被精心涂上一种颜色。然而，这片森林有一种特殊的规则，即任何两个相邻的节点或者通过一个节点相连的两个节点（即路径长度最多为 2 的节点）不能被涂上相同的颜色。诺伊的颜料盒中有 $C$ 种颜色供他选择。 诺伊希望知道有多少种不同的涂色方案，使得他的森林满足上述规则。由于这个数字可能非常大，所以请你帮他计算出这个数字模 $10^9 + 7$ 的结果。 注意： 两种涂色方案被认为是不同的，当且仅当至少存在一个节点在这两种方案中被涂上了不同的颜色。森林中的路径是指一系列连接的节点，路径长度是指路径中的边的数量。 ### 输入格式 输入的第一行将包含两个整数 $N$ 和 $C$，分别表示森林中的节点数量和诺伊颜料盒中的颜色数量。 接下来的 $N-1$ 行，每行包含两个整数 $U$ 和 $V$，表示存在一条边连接节点 $U$ 和节点 $V$。 数据范围保证：$1 \leq N \leq 10^5$，$1\leq C \leq 10^6$，$1 \leq U,V \leq N$。 ### 输出格式 输出一个整数，表示满足条件的涂色方案的数量对 $10^9 + 7$ 取模后的结果。 ### 样例输入 ``` 3 3 1 2 1 3 ``` ### 样例输出 ``` 6 ```