Migrated from Lutece 2493 yanje en yanje

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

——urushi - EXEC_SEED./

如果不想读这么长，可以直接跳到题面最后。

---

我做了一个悠长而又宁静的梦。

我梦见了周围有好多好多的浮空小岛。天空告诉我，一共有 $n$ 个小岛。

一些岛与岛之间有一座浮空桥，在天空俯视下这一定是一个树形结构吧。

我也想知道天空的眼睛下的景色，一定是五彩缤纷的吧：每一个岛都被染上了颜色。天空告诉我，每一座小岛都被染上了 $k$ 种颜色中的一种，并且两座岛之间有不多于两座浮空桥的话，它们的颜色也不相同。

那一定是十分美丽的世界吧......

天空告诉我：像这样的世界有很多，但都满足之前说的那样，“每一座小岛都被染上了 $k$ 种颜色中的一种，并且两座岛之间有不多于两座浮空桥的话，它们的颜色也不相同”。

原来有很多的吗......可我还真是不幸啊，一不小心就在这样的世界里出生了啊。

那是一个没有塔的世界。没有塔，也就没有所谓圣女这个概念。

自从那个梦之后，我对现在这个世界感到十分的厌倦而又无奈。

人们为了自己的生存，总会作出一些牺牲，可真是讽刺。

一想到那样的世界，我又不禁苦笑起来：明明只是一个梦而已，而那样的世界的数量庞大到我自己也不敢相信。

或许这就是我这性格养成的原因吧，我很想逃离这个世界，逃离这可笑的命运。

什么圣女......什么侍奉，这不过是人类为了掩盖这背后的真相而做出的装饰而已。

但后来，发生了一件奇妙的事，让我感觉到还有一丝希望。

通常人们都会对这个故事感到可笑，毕竟这只是理想中的世界，而我所在的地方就是现实。

但他.......Bob，对此并不在意。

「那样的世界确实很美好呢，我大概数了一下具体有多少，你看看。」

这让我有些惊讶：我从来不敢去想具体有多少，但只知道数量会很多，多到让我充满了愤怒与恐惧。

但是，他的答案也太小了，按理说在一些情况下肯定会超过 $10^{10}$ 的啊。

「你说这个啊，我只是对 $10^9+7$ 取了个模而已。」

这让我又惊又喜：本来是一个天文数字，但就这么写的话，这种落差感还真有一点欣慰呢。

但这也并不能改变现实。

我能在这样的世界出生，甚至可以说是不可能的事件，但还是发生了。

我叹了一口气，走向他，问道：

「那就快告诉我，你是怎么算的？」

---

$n$ 座浮空岛连成一棵树，现在要用 $k$ 种颜色给每一座浮空岛染其中一种颜色，并且若两座浮空岛之间的最短距离小于等于 $2$，那么这两座浮空岛不能染上相同颜色。那么一共有多少种染色方式？答案对 $10^9+7$ 取模。

Input

第一行两个正整数 $n,k$，代表一共有 $n$ 座浮空岛，颜色的一共有 $k$ 种；

接下来 $n-1$ 行，每行两个正整数 $x,y$，代表浮空岛 $x$ 和 $y$ 之间有一座浮空桥。

Output

一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

Samples

4 4
1 2
2 3
2 4

24

4 3
1 2
2 3
2 4

0

5 7
1 2
2 3
3 4
3 5

4200

Constraints

$1\le n,k\le 10^5$

Resources

2020 UESTC ICPC Training for Math and Geometry