[国家集训队] Crash 的文明世界

题目描述

Crash 小朋友最近迷上了一款游戏——文明5 (Civilization V)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。 现在 Crash 已经拥有了一个 $n$个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此 Crash 只修建了 $n-1$条道路连接这些城市,不过可以保证任意两个城市都有路径相通。 在游戏中,Crash 需要选择一个城市作为他的国家的首都,选择首都需要考虑很多指标,有一个指标是这样的: $$S(i) = \sum_{j = 1}^{n}{\rm dist}(i, j) ^ k$$ 其中 $S(i)$表示第 $i$个城市的指标值,${\rm dist}(i, j)$表示第 $i$个城市到第 $j$个城市需要经过的道路条数的最小值,$k$为一个常数且为正整数。 因此 Crash 交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数$\rm mod\ 10007$的值。

输入输出格式

输入格式


输入的第一行包括两个正整数 $n$和 $k$。 接下来有 $n-1$行,每行两个正整数 $u, v(1≤u, v≤n)$,表示第 $u$个城市和第 $v$个城市之间有道路相连。这些道路保证能符合题目的要求。

输出格式


输出共 $n$行,每行一个正整数,第 $i$行的正整数表示第 $i$个城市的指标值$\rm mod\ 10007$的值。

输入输出样例

输入样例 #1

5 2
1 2
1 3
2 4
2 5

输出样例 #1

10
7
23
18
18

说明

$20 \%$的数据满足 $n≤ 5000,k≤ 30$。 $50 \%$的数据满足 $n≤ 50000,k≤30$。 $100 \%$的数据满足 $n≤ 50000,k≤ 150$。