### 问题描述 圣诞节快到了，小明为了烘托圣诞节的气氛，购买了一颗树，但是这棵树一开始是任何装饰品的，小明想要用他的方法来装扮这棵圣诞树。 这棵圣诞树有 $n$ 个结点，这 $n$ 个结点通过 $n-1$ 条边连成一棵树，而小明手里拥有 $m$ 种颜色的挂件，小明想用这 $m$ 种颜色的挂件来装扮这棵圣诞树，并且想让这棵圣诞树中所有相邻的结点拥有不同的颜色。 小明想知道用这 $m$ 种挂件装扮这颗圣诞树的所有满足相邻结点颜色不同的总方案数量，你能帮帮他吗。注意，**不一定要将所有颜色都用上**。由于答案可能很大，将得出的答案对 $10^9+7$ 求余。 ### 输入格式 第一行，两个正整数 $n$ $(1\leq n\leq 10^5)$ 和 $m$ $(1\leq m \leq10^9)$ ，代表这颗圣诞树拥有 $n$ 个结点，以及小明手里有 $m$ 种颜色的挂件。 接下来 $n-1$ 行，每行两个正整数，格式如下： - ```l r``` $(1\leq l\leq n)$ ，$(1\leq r\leq n)$ ， 代表结点 $l$ 和结点 $r$ 之间有一条边将它们相连。 ### 输出格式 一行，一个正整数，代表所有可能的方案的数量，将结果对 $10^9+7$ 求余。 ### 输入样例 1 ``` 2 2 1 2 ``` ### 输出样例 1 ``` 2 ``` ### 输入样例 2 ``` 5 3 1 2 1 3 2 4 2 5 ``` ### 输出样例 2 ``` 48 ``` ### 样例说明 样例一中，小明的涂色方案只有 $[颜色1,颜色2],[颜色2,颜色1]$ 两种。