Minimum Spanning Trees

One day, Subconscious faced a problem that reminded him of a horrible experience in a past contest. In that contest, the easiest problem asked for the number of minimum spanning trees in a randomly generated graph.

Now there is a graph with $n$ vertices labeled from 1 to $n$. For each pair of vertices $u$ and $v$ ($1 \le u < v \le n$), there is no edge between them with probability $p_0/100$, or an edge of weight 1 with probability $p_1/100$, or an edge of weight 2 with probability $p_2/100$, and so on, up to an edge of weight $k$ with probability $p_k/100$, where $k$ is the maximum weight of an edge. All edges are generated independently.

The task is not to find the expected weight of the minimum spanning tree, since the graph may be disconnected and the task author does not know how to deal with such cases. Instead, for each integer $s$ between $n - 1$ and $k(n - 1)$, calculate the probability that the graph is connected and the weight of its minimum spanning tree is exactly $s$.

Subconscious thinks he has solved the problem, but he is not sure his solution is correct. He wants to check the answers modulo 1,000,000,007 with you.

The input contains several test cases. The first line contains a single integer $T$ ($1 \le T \le 200$), the number of test cases.

Each test case starts with two integers $n$ ($2 \le n \le 40$) and $k$ ($1 \le k \le 4$), the number of vertices and the maximum edge weight. The next line contains $k + 1$ non-negative integers $p_0, p_1, \ldots, p_k$ with $\sum_{i=0}^{k} p_i = 100$.

At most 20 test cases have $n > 10$, and at most 2 test cases have $n > 20$.

For each test case, print one line with $(k - 1)(n - 1) + 1$ integers. The $i$-th integer is the probability that the graph is connected and its minimum spanning tree has weight exactly $n - 2 + i$, reported modulo 1,000,000,007.

More precisely, if the reduced fraction of the probability is $p/q$, print the minimum non-negative integer $r$ such that $q \cdot r \equiv p \pmod{1000000007}$. You may assume such $r$ always exists in all test cases.