Marjar University has decided to upgrade the infrastructure of school intranet by using fiber-optic technology. There are `N` buildings in the school. Each building will be installed with one router. These routers are connected by optical cables in such a way that there is exactly one path between any two routers.

Each router should be initialized with an operating frequency `F _{i}` before it starts to work. Due to the limitations of hardware and environment, the operating frequency should be an integer number within [

Edward is the headmaster of Marjar University. He is very interested in the number of different ways to initialize the operating frequency. Please write a program to help him! To make the report simple and neat, you only need to calculate the sum of `F _{i}` (modulo 1000000007) in all solutions for each router.

There are multiple test cases. The first line of input contains an integer `T` indicating the number of test cases. For each test case:

The first line contains one integer `N` (1 <= `N` <= 50). The next line contains `N` integers `L _{i}` (1 <=

For the next `N` - 1 lines, each line contains two integers `X _{i}` and

For each test case, output a line with `N` integers representing the sum of `F _{i}` (modulo 1000000007) in all solutions.

提交代码