P4827 [集训队互测 2011] 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$ 的值。

无

无

对于 $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$。