CF2002H.Counting 101

题目背景

夏日漫长，蝉鸣不断，酷暑难耐。终于，它落下了帷幕。决战已过，大门敞开，只留下一阵轻风。

你的前辈们已经完成了最后的鞠躬，轮到你上场了。

在整理留下的一些笔记时，你发现了一份名为 问题 101 的奇怪声明：

• 给定一个正整数序列 $a_1,a_2,\ldots,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,\ldots,\left\lfloor\frac{n-1}{2}\right\rfloor$，求元素在 $[1, m]$ 中的整数序列 $a_1,a_2,\ldots,a_n$ 的个数，使得作为 问题 101 的输入时，答案是 $k$。由于答案可能非常大，只需要输出对 $10^9+7$ 的结果即可。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1\le t\le10^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=8$ 种合法数组。其中 $[1,2,1]$ 与 $[1,1,1]$ 可操作一次，余下 $6$ 个数组无法操作。