SOLVE
LATER
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:
Phillipe selects a connected subset of the cities, i.e. a connected subgraph of the tree.
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.
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 \).
The connected subgraphs are:
1, contest types: 1, pass type: 1
2, contest types: \( \{ 1,2 \} \), pass type: 2
3, contest types: 2, pass type: 1
\( \{ 1,2 \} \), contest types: 1, pass type: 1
\( \{ 1,3 \} \), contest types: \(\emptyset\), pass type: 0
\( \{ 1,2,3 \} \), contest types: \(\emptyset\), pass type: 0
Hence, the answer is \( [2,3,1] \).