TREESUM - Tree Sum

no tags 

Let Lx denote the level of a node x in a rooted tree. Lx is 1 if x is the root, otherwise Lx = 1 + Ly, where y is the parent of x in the rooted tree.

You need to calculate the sum Lx ^ K for all nodes x in the tree.

Input

The first line contains the number of test cases T. T test cases follow. The first line of each test case contains N and K, where N is the number of nodes in the tree. The following N - 1 lines contain two integers ai and bi, indicating an edge between nodes ai and bi in the tree. There is a blank line after each test case.

Output

Output N lines for each test case. The i-th line should contain the required sum if the tree is rooted at node i. Output all values modulo 1000000007. Output a blank line after each test case.

Example

Sample Input:
2
3 2
0 1
1 2

3 3
0 1
0 2

Sample Output:
14
9
14

17
36
36

Constraints

1 <= T <= 10
1 <= N <= 20000
1 <= K <= 20
0 <= ai, bi < N


hide comments
bhim: 2014-10-29 14:16:17

Last edit: 2014-11-03 16:19:27
Yusro Tsaqova: 2013-06-15 10:49:55

nice problem !!

ulasuevoli: 2011-08-23 00:30:01

Really a Nice Problem!

Kazi Rakibul Hossain: 2011-08-23 00:30:01

excellent problem


Added by:Varun Jalan
Date:2010-09-20
Time limit:1.570s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem, used for Al Khwarizm '10