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 distK 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 109+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 109+7.
Constraints
2 ≤ N ≤ 105
1 ≤ K ≤ 109