최소 신장 트리

어느 날 Subconscious는 지난 대회에서 겪었던 끔찍한 경험이 떠오르는 문제를 마주했다. 그 대회에서 가장 쉬운 문제는 무작위로 생성된 그래프에서 최소 신장 트리의 개수를 세는 것이었다.

이제 $1$부터 $n$까지 번호가 붙은 $n$개의 정점으로 이루어진 그래프가 있다. 정점 쌍 $u$, $v$ ($1 \le u < v \le n$)마다 두 정점 사이에 간선이 없을 확률은 $p_0/100$, 가중치가 1인 간선이 있을 확률은 $p_1/100$, 가중치가 2인 간선이 있을 확률은 $p_2/100$, 이하 같은 방식으로 가중치가 $k$인 간선이 있을 확률은 $p_k/100$이다. 여기서 $k$는 간선의 최대 가중치다. 모든 간선은 서로 독립적으로 생성된다.

그래프가 연결되지 않을 수도 있으므로 최소 신장 트리 가중치의 기댓값을 구하는 것이 아니다. 대신 $n - 1$ 이상 $k(n - 1)$ 이하의 각 정수 $s$에 대해, 그래프가 연결되어 있고 최소 신장 트리의 가중치가 정확히 $s$일 확률을 구하라.

Subconscious는 이 문제를 풀었다고 생각하지만 자신의 풀이가 맞는지 확신하지 못한다. 그래서 답을 $1,000,000,007$로 나눈 나머지 기준으로 당신과 함께 확인하려 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 개수 $T$ ($1 \le T \le 200$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 개수 $n$ ($2 \le n \le 40$)과 간선의 최대 가중치 $k$ ($1 \le k \le 4$)가 주어진다. 다음 줄에는 음이 아닌 정수 $p_0, p_1, \ldots, p_k$가 공백으로 구분되어 주어지며, $\sum_{i=0}^{k} p_i = 100$이다.

$n > 10$인 테스트 케이스는 최대 20개이고, $n > 20$인 테스트 케이스는 최대 2개임이 보장된다.

각 테스트 케이스마다 $(k - 1)(n - 1) + 1$개의 정수를 한 줄에 출력한다. $i$번째 정수는 그래프가 연결되어 있고 최소 신장 트리의 가중치가 정확히 $n - 2 + i$인 확률을 $1,000,000,007$을 법으로 한 나머지다.

더 정확히 말하면, 확률을 기약분수 $p/q$로 나타냈을 때 $q \cdot r \equiv p \pmod{1000000007}$을 만족하는 0 이상의 가장 작은 정수 $r$을 출력한다. 모든 테스트 케이스에서 그러한 $r$이 항상 존재한다고 가정해도 된다.