这是一个漫长的夏日,蝉鸣不断,炎热似乎永无休止。终于,它已经接近尾声了。决战已过,大门敞开,只剩下微风徐徐。
你们的前辈们已经最后鞠躬了;轮到你上台了。
整理一些留下的笔记,你发现了一个奇怪的陈述,名为问题 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$$$ 为模。
示例
输入 #1
2 3 2 10 10
输出 #1
6 2 1590121 23399118 382293180 213020758 379696760
注意
在第一个测试用例中,有 $$$2^3=8$$$ 候选序列。其中,可以对$$$[1,2,1]$$$和$$$[1,1,1]$$$操作一次;您不能对其他 $$$6$$$ 序列进行操作。