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
5 3 1 2 3 2 4 3 3 5
90
Magicland has 5 cities and 4 roads: (1, 2), (3, 2), (4, 3), (3, 5).
There are 10 pairs of cities.
4 of them are directly connected by a road and thus Kevin will pay 4 * 13 = 4 for them in total.
For the other 4 pairs of cities the distance is equal to 2 and Kevin will pay 23 = 8 for each of them, 4*8 = 32 in total.
And the last 2 pairs have the distance equal to 3 and Kevin must pay 2 * 33 = 54 for them.
The total cost is 4 + 32 + 54 = 90.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor