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

숭실대학교를 다니는 근형이는 고려대학교 동아리 MatKor의 부원으로도 활동하고 있다. 근형이는 MatKor에서 진행하는 <그 유명한 LCS 시리즈 모두 풀어 보기> 세미나를 들었다.

근형이는 숭실대학교 동아리 SCCC가 즐기는 수열 만들기 놀이에 LCS를 접목하면 재미있겠다고 생각했다. 놀이는 다음과 같다. 먼저 양의 정수 $K$를 하나 정한다. 그다음 놀이에 참여하는 $M$명의 부원이 각자 독립적으로 아래 과정을 수행한다.

• 빈 종이가 하나 주어진다. 종이에 $K$가 적힐 때까지 아래를 반복한다.
  • $1$ 이상 $K$ 이하의 정수 중 하나를 균등한 확률로 뽑는다.
  • 뽑은 수가 종이에 적힌 모든 수보다 크면 그 수를 맨 뒤에 적는다.

놀이가 끝나면 $M$명의 부원은 각자 길이 $K$ 이하의 수열을 하나씩 갖게 된다. 이 수열을 $A\_1,A\_2,\cdots ,A\_M$이라고 하자.

근형이는 $\operatorname{LCS}(A\_1,A\_2,\cdots ,A\_M)$의 길이의 기댓값을 $f(K,M)$이라 할 때, $f(1,M), f(2,M), \cdots, f(N,M)$의 값을 모두 알고 싶다. 근형이를 도와 답을 구하라.

여기서 $\operatorname{LCS}(A\_1,A\_2,\cdots ,A\_M)$은 모든 $A\_i$의 부분 수열 중 가장 긴 공통 부분 수열을 뜻한다. 부분 수열은 주어진 수열에서 순서를 바꾸지 않고 $0$개 이상의 원소를 삭제해서 얻을 수 있는 수열이다.

첫 번째 줄에 양의 정수 $N(1\le N\le 10^6)$과 $M(1\le M\le 10^{18})$이 공백으로 구분되어 주어진다.

첫 번째 줄에 $f(1,M), f(2,M), \cdots, f(N,M)$의 길이의 기댓값을 각각 $10^9+7$로 나눈 나머지를 공백으로 구분하여 출력한다.

기약 분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는, $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수 $q^{-1}$, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원을 이용해 $p\cdot q^{-1}\pmod M$로 정의한다. 정수인 경우 $q=q^{-1}=1$이므로 $p\pmod M$을 뜻한다.

주어진 조건에서 기댓값은 정수이거나, 분모가 $10^9+7$의 배수가 아닌 유리수로 나타낼 수 있음을 증명할 수 있다.