$\mathbb{E}\left(\operatorname{LCS}\right)$

Geunhyeong attends Soongsil University and is also a member of the MatKor club at Korea University. He took the seminar run by MatKor titled <Solve All the Famous LCS Series>.

Geunhyeong wondered whether adding LCS to the number sequence game played by the SCCC club at Soongsil University would be fun. The game works as follows. First, pick a positive integer $K$. Then each of the $M$ members who take part performs the following independently.

• A blank sheet of paper is given. Repeat the steps below until $K$ is written on the sheet.
  • Draw one integer from 1 to $K$ inclusive, each with equal probability.
  • If the drawn number is larger than every number already on the sheet, write it at the end.

After the game ends, each of the $M$ members holds one sequence of length at most $K$. Call these sequences $A\_1,A\_2,\cdots ,A\_M$.

Geunhyeong wants the values of $f(1,M), f(2,M), \cdots, f(N,M)$, where $f(K,M)$ is the expected length of $\operatorname{LCS}(A\_1,A\_2,\cdots ,A\_M)$. Help him find them.

Here $\operatorname{LCS}(A\_1,A\_2,\cdots ,A\_M)$ is the longest common subsequence of all $A\_i$. A subsequence is obtained by deleting zero or more elements from a sequence without changing the order of the remaining elements.

The first line contains two positive integers $N(1\le N\le 10^6)$ and $M(1\le M\le 10^{18})$, separated by a space.

Print the expected lengths $f(1,M), f(2,M), \cdots, f(N,M)$ on the first line, separated by spaces, each reduced modulo $10^9+7$.

For an irreducible fraction $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$, its value modulo $M$ is defined as $p\cdot q^{-1}\pmod M$, where $q^{-1}$ is the integer satisfying $q\cdot q^{-1}\equiv 1\pmod M$, that is, the modular multiplicative inverse of $q$ modulo $M$. If the value is an integer, then $q=q^{-1}=1$, so the result is $p\pmod M$.

Under the given constraints, the expected value is either an integer or a rational number whose denominator is not a multiple of $10^9+7$. This can be proven.