H. Подсчёт 101
ограничение по времени на тест
10.1 секунд
ограничение по памяти на тест
1010 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это был долгий летний день с постоянным стрекотанием цикад и жарой, которая, казалось, никогда не закончится. Наконец, он подошел к концу. Схватка прошла, ворота открыты, и только легкий ветерок остался позади.

Ваши предшественники отвесили последний поклон, теперь ваша очередь выйти на сцену.

Разбираясь в оставленных записях, вы нашли любопытное условие под названием Задача 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$$$ найдите количество целочисленных последовательностей $$$a_1,a_2,\ldots,a_n$$$ с элементами из $$$[1, m]$$$, таких, что при использовании их в качестве входных данных для задачи 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 2
10 10
Выходные данные
6 2 
1590121 23399118 382293180 213020758 379696760
Примечание

В первом наборе входных данных есть $$$2^3=8$$$ последовательностей-кандидатов. Среди них по одному разу можно оперировать с последовательностями $$$[1,2,1]$$$ и $$$[1,1,1]$$$; с остальными $$$6$$$ последовательностями оперировать нельзя.