有一天，Subconscious 遇到了一道题，这让他回想起了一次比赛中糟糕的经历。在那场比赛中，最简单的一道题要求计算一个随机生成的图中最小生成树的数量。

现在有一个包含 $n$ 个顶点的图，顶点编号从 $1$ 到 $n$。对于每一对顶点 $u$ 和 $v$ ($1 \le u < v \le n$)，它们之间不存在边的概率为 $\frac{p_0}{100}$，存在权值为 $1$ 的边的概率为 $\frac{p_1}{100}$，存在权值为 $2$ 的边的概率为 $\frac{p_2}{100}$，以此类推，存在权值为 $k$ 的边的概率为 $\frac{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$)，分别表示随机生成图的顶点数和边的最大权值。

接下来一行包含 $k + 1$ 个非负整数 $p_0, p_1, p_2, \dots, p_k$ ($\sum_{i=0}^k p_i = 100$)，描述了每对顶点之间边的概率分布。

保证满足 $n > 10$ 的测试用例不超过 $20$ 个，满足 $n > 20$ 的测试用例不超过 $2$ 个。

输出格式

对于每个测试用例，给定 $n$ 和 $k$，输出一行，包含 $(k - 1)(n - 1) + 1$ 个整数。其中第 $i$ 个整数表示图是连通的且最小生成树的权值恰好为 $n - 2 + i$ 的概率，结果对 $1\,000\,000\,007$ 取模。

更准确地说，如果概率的最简分数为 $\frac{p}{q}$，你需要提供满足 $q \cdot r \equiv p \pmod{1\,000\,000\,007}$ 的最小非负整数 $r$。你可以放心地假设在所有测试用例中这样的 $r$ 总是存在的。

样例

样例输入 1

2
3 1
50 50
3 2
0 50 50

样例输出 1

500000004
500000004 375000003 125000001