[国家集训队] 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 交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数 $\bmod\ 10007$ 的值。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

5 2
1 2
1 3
2 4
2 5

输出样例 #1

10
7
23
18
18

说明

对于 $20 \%$ 的数据,$n\le 5000$,$k\le 30$。 对于 $50 \%$ 的数据,$n\le 5\times 10^4$,$k\le 30$。 对于 $100 \%$ 的数据,$1\le n\le 5\times 10^4$,$1\le k\le 150$。