MatKor Cup 자리 배치

이번 MatKor Cup에는 총 $N$명의 참가자가 참가하였으며, 대회장에는 $M$개의 자리가 준비되어 있다. 종우는 $N$명의 참가자들에게 각각 서로 다른 자리를 한 개씩 미리 배정해 두었고, 동우가 종우에게 어떻게 자리를 배정했는지 물어보았다.

종우는 그냥 알려줄 수는 없고, 동우에게 $N$명의 자리를 예측해 보라고 했다. 동우는 $M$개의 자리 중 서로 다른 $N$개의 자리를 고른 후, 각 참가자의 자리를 예측했다.

동우가 예측한 $N$명 중, 종우가 배정한 자리와 같은 자리에 앉은 사람 수가 $i$명일 확률을 각각 구해보자.

종우와 동우는 가능한 모든 경우에 대해 동일한 확률로 자리를 배정하거나 예측한다.

첫 번째 줄에 참가 인원과 자리의 개수 $N,M(1\le N\le M\le 5\,000\,000)$이 공백으로 구분되어 주어진다.

첫 번째 줄에 동우가 예측한 $N$명 중, 종우가 배정한 자리와 같은 자리에 앉은 사람 수가 $i(0\le i \le N)$명일 확률을 $10^9+7$로 나눈 나머지를 한 줄에 출력한다. 이때, $0$부터 $N$까지 총 $N+1$개의 수를 공백으로 구분하여 출력해야 함에 유의하자.

기약 분수 $\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$의 배수가 아닌 유리수로 나타내어짐을 증명할 수 있다.