32236번 - $\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}\left( A_1,A_2,\cdots ,A_M \right)$의 길이의 기댓값을 $f\left( K,M \right)$이라 할 때, $f\left( 1,M \right) ,f\left( 2,M \right) ,\cdots ,f\left( N,M \right)$의 값을 모두 알고 싶다. 근형이를 도와 답을 구해보자.

여기서 $\operatorname{LCS}\left( A_1,A_2,\cdots ,A_M \right)$는 모든 $A_i$의 부분 수열 중 가장 긴 공통된 부분 수열을 의미하며, 부분 수열은 주어진 수열에서 순서를 바꾸지 않고 0ドル$개 이상의 원소를 삭제해서 얻을 수 있는 수열을 의미한다.

입력

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

출력

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

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

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

제한

서브태스크

힌트