The country of Berland consists of N cities, numbered 1 through N. The cities are connected by roads in such a way that there is exactly one way to reach any city from any other city without visiting some city twice. In other words, the road map is represented by a tree.

A company called Suarez runs M different types of programming contests throughout Berland. A programming contest of each type may or may not be held in a particular city; for each city and each contest type, you are given the information if a contest of this type is held in this city.

Now, a person called Phillipe wants to participate in these contests according to the following rules:

1. Phillipe selects a connected subset of the cities, i.e. a connected subgraph of the tree.

2. Then, Phillipe determines all types of programming contests such that a contest of that type may be held in every city from the subset chosen in step 1.

3. He then participates in all programming contests of types chosen in step 2 in all cities of the subset.

The Suarez company has a rule which states that to participate in programming contests of k distinct types, a contestant needs to use a k-pass (it's free though). Even a contestant that doesn't participate in any programming contest needs to use a 0-pass.

Phillipe performs the procedure described above for each connected subset of Berlandian cities independently. You need to find the number of k-passes he will buy modulo $10^9+7$, for each possible k.

Constraints

• $1 \le T \le 5$

• $1 \le N \le 5,000$

• $1 \le M \le 10$

• the input graph will be a tree

Input format

The first line of the input contains a single integer T denoting the number of test cases in one test file.

The first line of each test case contains two space-separated integers N and M.

Each of the next $N - 1$ lines contains two space-separated integers u and v, denoting an edge between vertices u and v.

Each of the next N lines contains M space-separated integers. The j-th integer on the i-th of these lines is 1 if a programming contest of type j is held in city i or 0 if it is not held in city i.

Output format

For each test case, print a single line containing $M+1$ space-separated integers. For each $0 \le k \le M$, the k-th of these integers should denote the number of k-passes Phillipe will buy, modulo $10^9+7$.