仿生人不会梦到彩色电子羊
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你回到家，感觉非常困，于是直接就睡觉了。

你梦到了一棵有 n 个节点的树。

你又梦到了一些羊，羊有 K 种颜色。

你想要在每个节点上放一头羊，使得相邻节点的羊颜色不同，因为你觉得这样不大美观。

你想要知道合法的方案数对 1000000007 取模的答案。

输入描述:

输入第一行两个正整数 n,K 。（1\le n\le 10^6,1\le K\le n）

接下来n-1行，每行两个正整数 u,v 。（1\le u,v\le n）

输出描述:

输出一行一个正整数表示答案。
示例1

输入

复制 
5 3
1 2
1 3
2 4
2 5

输出

复制 
48