Capital Evaluation in Civilization V

Crash is an enthusiastic player of Civilization V. In his game, he controls a country of n cities connected by n-1 roads so that any two cities are connected by a unique path (i.e. the road network is a tree). He must choose a capital based on various metrics. One of these metrics for city i is defined as:

[ S(i) = \sum_{j=1}^{n}{\rm dist}(i, j)^k ]

where \({\rm dist}(i, j)\) is the minimum number of roads needed to travel from city i to city j, and k is a given positive integer constant. Your task is to compute, for each city, the value of \(S(i)\) modulo 10007.

Note: The cities are numbered from 1 to n, and the road network is guaranteed to be connected.

inputFormat

The first line contains two integers n and k, where n is the number of cities and k is the exponent in the metric calculation. The next n-1 lines each contain two integers u and v, indicating that there is a road connecting city u and city v.

outputFormat

Output n lines. The i-th line should contain the value of \(S(i)\) modulo 10007.

sample

4 1
1 2
2 3
2 4

5
3
5
5