题目描述

树中节点的深度是其父节点的深度加一,其中根节点的深度为1。

给定一棵n个点的无根树和一个整数k。记d[x,y]表示点x作为根时,节点y的深度。对于每个x(1<=x<=n),请你求出(\sum_{y=1}^{n} d[x,y]^{k}) mod (10^{9}+7)

输入格式

每个测试点包含不超过10组数据,每组数据的第一行是两个整数N和K,接下来N-1行每行两个整数a、b,表示有一条连接a和b的边。输入以EOF结束。

输出格式

对于每组数据输出n行,第i行表示点i为根时(\sum_{j=1}^{n} d[i,j]^{k}) mod (10^{9}+7) 的值。相邻两组数据之间用一个空行隔开。

样例输入

3 2
1 2
2 3
3 3
1 2
1 3

样例输出

14
9
14
 
17
36
36

数据范围与约定

对于30%的数据,1<=n<=500。

对于100% 的数据,1<=a,b<=n<=20000,1<=k<=20。