TREESUM  Tree Sum
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 ith 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:
20141029 14:16:17
Last edit: 20141103 16:19:27 

Yusro Tsaqova:
20130615 10:49:55
nice problem !! 

ulasuevoli:
20110823 00:30:01
Really a Nice Problem! 

Kazi Rakibul Hossain:
20110823 00:30:01
excellent problem 
Added by:  Varun Jalan 
Date:  20100920 
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 