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≤u<v≤n), there will be no edge between them with probability p0100, or an edge of weight 1 with probability p1100, or an edge of weight 2 with probability p2100, ..., or an edge of weight k with probability pk100, 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 1000000007 with you.
Input
The input contains several test cases, and the first line contains a single integer T (1≤T≤200), the number of test cases.
For each test case, the first line contains two integers n (2≤n≤40) and k (1≤k≤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 p0,p1,p2,⋯,pk (∑ki=0pi=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.
Output
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 1000000007.
More precisely, if the reduced fraction of the probability is pq, what you should provide is the minimum non-negative integer r such that qr≡p(mod1000000007). You may safely assume that such r always exists in all test cases.