题目背景

小萝卜是远近闻名的军师呢（自豪脸）。

不过最近，如果你要找她请教，那么她就会大喊一声：那！我！问！你！

你愿意和他（她）一直在一起吗？你能接受被拒绝被分手吗？你能为了他付出多少呢？你能保证完成自己许下的诺言吗？

——不过萝卜还是很愿意帮忙的，尽管她已经见证了若干自己促成的人们分手了……生气啊啊啊啊啊！

题目描述

萝卜有 $m$ 件衣服，计划表为长为 $n$ 的序列 $a$，则 $a_i$ 为 $[1,m]$ 中的整数，表示当天穿的是哪一件衣服。
现在给定 $a$，萝卜每次修改可以将 $a_i$ 修改为 $[1,m]$ 中任何一个整数，要求在使得序列中相邻的两个数都不同的前提下，让修改次数最少。

小萝卜的朋友很多，她们也希望和自己的意中人出去玩，她要以此为切入点评判这些情感问题。

具体的，对于一个表示计划表的序列 $a$，令困难程度 $f(a,n,m)$ 表示以上问题的答案，$g(a,n,m)$ 表示使答案最优的修改方案数。其中两个方案不同当且仅当修改后的序列不同。

在所有长为 $n$ 值域为 $[1,m]$ 的整数序列中，对于每个 $i\in[0,\lfloor\frac{n}2\rfloor]$，小萝卜想知道困难程度为 $i$ 的序列的最优修改方案数之和是多少。

形式化的，给定 $n,m$，令所有长为 $n$ 值域为 $[1,m]$ 的整数序列的集合为 $S$，则对每个 $i\in[0,\lfloor\frac{n}2\rfloor]$ 求：

$$\sum\limits_{a\in S}[f(a,n,m)=i]g(a,n,m)$$

答案对 $10^9+7$ 取模。

输入格式

一行两个正整数 $n,m$。

输出格式

一行 $\lfloor\frac{n}2\rfloor+1$ 个非负整数，其中第 $k$ 个为 $i=k-1$ 时的答案。

3 2

2 6

4 5

320 1760 1280

11 4514

381390190 652303527 170625074 922115722 774772088 111358420

提示

【样例解释】

对于样例 $1$，所有可能的序列以及对应的 $f,g$ 函数值如下：

• $[1,1,1]$：$1,1$。
• $[1,1,2]$：$1,1$。
• $[1,2,1]$：$0,1$。
• $[1,2,2]$：$1,1$。
• $[2,1,1]$：$1,1$。
• $[2,1,2]$：$0,1$。
• $[2,2,1]$：$1,1$。
• $[2,2,2]$：$1,1$。

故 $i=0$ 时答案为 $2$，$i=1$ 时答案为 $6$。

对于样例 $2,3$，暂时不能给你一个明确的答复。

【数据范围】

本题开启捆绑测试。

子任务	分数	$n\le$	$m\le$
$1$	$7$	$9$	$5$
$2$	$10$	$5\times10^3$	$2$
$3$	$13$	$50$
$4$	$15$	$200$	$200$
$5$	$20$		$10^9$
$6$	$35$	$5\times10^3$

对于 $100\%$ 的数据，$1\le n\le 5\times10^3$，$2\le m\le 10^9$。