13179번 - 비트

시간이 많은 그는 N개의 비트(0 또는 1을 가질 수 있는 변수)를 조작하는 일을 반복하고 있다. 지금까지 하던 것이 식상해진 그는 새로운 규칙으로 N개의 비트를 조작하려고 한다. 한 번의 조작이란 다음과 같은 작업을 의미한다.

1. 비트 중에서 0인 것들을 먼저, 1인 것들을 나중에 놓는 방식으로 일렬로 늘어 놓는다. 즉 오름차순(엄밀히 비내림차순) 정렬한다.
2. 그 다음 1 이상 N 이하의 정수 K개(K는 홀수)를 무작위로 뽑는다. 각 정수를 뽑을 확률은 모두 독립적으로, 같은 정수가 두 번 이상 뽑힐 수도 있으며, 1부터 N 까지의 각 자연수가 뽑힐 확률은 모두 동일하다.
3. 뽑힌 K 개의 정수 각각에 대해서 정수가 i 라면 i 번째 비트를 토글한다. 즉, 0이면 1로, 1이면 0으로 바꾼다.

예를 들어, 그가 가진 비트가 0,1,0이고 K = 3이라고 해보자.

1. 먼저 비트를 정렬하여 0,0,1로 만든다.
2. K = 3개의 정수를 뽑아 1,3,1순서대로 뽑혔다고 해보자.
3. 첫 번째 정수 1에 의해서 비트는 1,0,1이 된다. 두 번째 정수 3에 의해서 비트는 1,0,0이 된다. 세 번째 정수 1에 의해서 비트는 0,0,0이 된다.

위의 과정에서 알 수 있듯, 사실 비트의 순서가 어떻게 되어있는지는 크게 중요한 것이 아니고 개수가 중요하다. 그는 조작을 한 후에 모든 비트가 1이 되면 조작을 끝내고 자러 갈 것이다. 현재 비트 중에서 0인 것의 개수가 z개일 때 모든 비트를 1로 만들기 위한 조작 횟수의 기댓값을 구하는 프로그램을 작성하라.

첫 번째 줄에는 비트의 개수와 뽑게 되는 정수의 개수를 의미하는 두 자연수 N, K가 공백으로 구분되어 주어진다. K는 홀수이다. (1 ≤ N ≤ 100, 0 ≤ K ≤ 10⁹)

N개의 줄에 걸쳐 답을 출력한다. z번째 줄에는 현재 비트 중에서 0인 것의 개수가 z개일 때 모든 비트를 1로 만들기 위해 필요한 조작 횟수의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b^-1) mod 1,000,000,007을 대신 출력하도록 한다. b^-1은 b의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.