Optimal Modification Schemes Counting

Given two positive integers \(n\) and \(m\), consider all integer sequences \(a = [a_1,a_2,\dots,a_n]\) with each \(a_i \in [1,m]\). A sequence represents a daily clothing schedule where \(a_i\) is the clothing worn on day \(i\).

For a given sequence \(a\), one is allowed to modify any element \(a_i\) to any integer in \([1,m]\) so that in the final sequence \(b\) it holds that \[ b_i \neq b_{i+1} \quad\text{for } 1 \le i < n. \] However, the modifications should be performed as few as possible. Let the difficulty \(f(a,n,m)\) be the minimum number of modifications needed to get a sequence with no adjacent equal elements, and let \(g(a,n,m)\) be the number of ways (i.e. distinct resulting sequences) to achieve that optimum.

Now, for every sequence \(a\) of length \(n\) (where \(a_i\in[1,m]\)) let \(f(a,n,m)\) and \(g(a,n,m)\) be defined as above. For each \(i\) with \(0\le i\le \lfloor n/2 \rfloor\), compute \[ \sum_{a\in S}[f(a,n,m)=i]\, g(a,n,m) \pmod{10^9+7}, \] where \(S\) is the set of all \(m^n\) sequences and \([f(a,n,m)=i]\) is the indicator function.

Explanation: A useful observation is that any sequence \(a\) can be divided into consecutive segments (or "runs") of equal numbers. For a segment of length \(L\), one can show that the minimum modifications needed is \(\lfloor L/2 \rfloor\). Moreover, there are:

• For \(L=1\): exactly 1 way (do nothing).
• For even \(L\): 2 ways to choose an alternating pattern (either modify the even-indexed positions or the odd-indexed positions) with each modification having \(m-1\) possible choices; that is, \(2\cdot (m-1)^{L/2}\) ways.
• For odd \(L\) (with \(L\ge3\)): only one valid alternating pattern, with \((m-1)^{\lfloor L/2 \rfloor}\) ways.

In addition, note that when a sequence splits into multiple segments, the chosen values for consecutive segments must differ (which contributes a factor of \(m-1\) for every segment after the first, with the first segment having \(m\) choices). Combining these factors, one may show that the total for a fixed sequence \(a\) is \[ m\cdot (m-1)^{k-1+\sum_{j=1}^k \lfloor L_j/2 \rfloor}\cdot 2^{\#\{j: L_j \text{ is even}\}}, \] where \(k\) is the number of segments and \(L_1,L_2,\dots,L_k\) are their lengths.

Your task is to compute, for each \(i = 0,1,2,\dots,\lfloor n/2 \rfloor\), the sum over all sequences \(a\) with \(f(a,n,m)=i\) of \(g(a,n,m)\) modulo \(10^9+7\).

inputFormat

The input consists of a single line containing two integers \(n\) and \(m\) (\(1 \le n, m \le \text{some reasonable limit}\)).

outputFormat

Output \(\lfloor n/2 \rfloor+1\) space-separated integers, where the \(i\)-th number (0-indexed) is the sum of \(g(a,n,m)\) over all sequences \(a\) with \(f(a,n,m)=i\), modulo \(10^9+7\).

sample

1 1

1