Это был долгий летний день с постоянным стрекотанием цикад и жарой, которая, казалось, никогда не закончится. Наконец, он подошел к концу. Схватка прошла, ворота открыты, и только легкий ветерок остался позади.
Ваши предшественники отвесили последний поклон, теперь ваша очередь выйти на сцену.
Разбираясь в оставленных записях, вы нашли любопытное условие под названием Задача 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\).
Выходные данные
Для каждого набора входных данных выведите \(\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\) последовательностями оперировать нельзя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 2
10 10
|
6 2
1590121 23399118 382293180 213020758 379696760
|