H. 计数 101
每个测试点时间限制：$10.1$ 秒
内存限制：$1010$ MB

那是一个漫长的夏日，蝉鸣不止，暑气似乎永无休止。终于，这一天落下了帷幕。决战已经过去，大门敞开，只留下一缕微风。

你的前辈们已经谢幕；现在轮到你登场了。

你在整理一些遗留的笔记时，发现了一个名为“问题 101”的有趣描述：

给定一个正整数序列 $a_1, a_2, \dots, a_n$，你可以对它进行任意次操作。
在每次操作中，你选择三个连续元素 $a_i, a_{i+1}, a_{i+2}$，将它们合并成一个元素 $\max(a_i + 1, a_{i+1}, a_{i+2} + 1)$。
请计算在不产生大于 $m$ 的元素的前提下，最多能进行多少次操作。

经过一番思考，你决定提出以下问题，名为“计数 101”：

给定 $n$ 和 $m$。对于每个 $k = 0, 1, \dots, \left\lfloor \frac{n-1}{2} \right\rfloor$，求出满足以下条件的整数序列 $a_1, a_2, \dots, a_n$ 的数量：
序列中每个元素在 $[1, m]$ 范围内，且作为“问题 101”的输入时，答案为 $k$。
由于答案可能非常大，请将其对 $10^9 + 7$ 取模后输出。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。接下来是每个测试用例的描述。

每个测试用例的一行包含两个整数 $n$、$m$（$1 \le n \le 130$，$1 \le m \le 30$）。

输出格式

对于每个测试用例，输出 $\left\lfloor \frac{n+1}{2} \right\rfloor$ 个数。
第 $i$ 个数表示使得“问题 101”的答案为 $i-1$ 的合法序列数量，对 $10^9 + 7$ 取模后的值。

示例

输入

2
3 2
10 10

输出

6 2 
1590121 23399118 382293180 213020758 379696760 

说明

在第一个测试用例中，共有 $2^3 = 8$ 个候选序列。
其中，可以对 $[1,2,1]$ 和 $[1,1,1]$ 进行一次操作；其余 $6$ 个序列无法进行操作。