Minimum Spanning Trees

One day, Subconscious is facing a problem that reminds him of the horrible experience in a past contest. In that contest, the easiest problem requires to count 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 will be no edge between them with probability $\frac{p_0}{100}$, or an edge of weight $1$ with probability $\frac{p_1}{100}$, or an edge of weight $2$ with probability $\frac{p_2}{100}$, ..., or an edge of weight $k$ with probability $\frac{p_k}{100}$, where $k$ is the maximum weight of an edge.

However, your task is not finding the expected weight of the minimum spanning tree of the randomly generated graph since the graph may be disconnected and the task author does not know how to deal with such cases.

Thus, your task becomes, for each integer $s$ between $n-1$ and $k(n-1)$, calculating the probability that the graph is connected and the weight of the minimum spanning tree of the graph is exactly $s$.

The problem is so hard that even if our talent Subconscious has managed to solve it, he is not sure whether his solution works and wants to check the answers modulo $1\,000\,000\,007$ with you.

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

For each test case, the first line contains two integers $n~(2 \le n \le 40)$ and $k~(1 \le k \le 4)$, denoting the number of vertices of the randomly generated graph and the maximum weight of an edge.

The following line contains $k+1$ non-negative integers $p_0, p_1, p_2, \cdots, p_k~(\sum_{i=0}^{k}p_i = 100)$, describing the probability distribution of an edge between each pair of vertices.

It's guaranteed that no more than $20$ test cases satisfy $n>10$ and no more than $2$ test cases satisfy $n>20$.

For each test case, with given $n$ and $k$, output a line containing $(k-1)(n-1)+1$ integers, the $i$-th of which is the probability that the graph is connected and the weight of the minimum spanning tree of the graph is exactly $n-2+i$, modulo $1\,000\,000\,007$.

More precisely, if the reduced fraction of the probability is $\frac{p}{q}$, what you should provide is the minimum non-negative integer $r$ such that $q r \equiv p \pmod{1\,000\,000\,007}$. You may safely assume that such $r$ always exists in all test cases.

2
3 1
50 50
3 2
0 50 50

500000004
500000004 375000003 125000001

2019 Multi-University Training Contest 10