The country of Magicland has N cities (numbered 1 through N) and N-1 bidirectional roads. Each road connects two different cities. There is a unique path between each pair of cities. All roads in the country have the same length, equal to 1.

Magicland also has the bus service. It allows citizens to ride between any pair of cities at the cost of dist^K where K is a fixed integer, and dist denotes the distance between the two cities.

Kevin lives in Magicland and is going on an adventure. He wants to travel between every pair of cities exactly once by riding on buses. Note that there are exactly N(N-1)/2 pairs of cities. He is wondering how much it will cost him in total. Find the total cost and print it modulo 10⁹+7.

Input format

The first line contains two integers N and K.

The next N-1 lines contain 2 integers each, denoting two cities connected by a road.

Output format

In a single line print the answer modulo 10⁹+7.

Constraints

2 ≤ N ≤ 10⁵
1 ≤ K ≤ 10⁹