비트 Batch Compilation commands

시간이 많은 그는 $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$는 홀수이다.

부분문제

부분문제	점수	N	K
1	9	1 ≤ N ≤ 100	K = 1
2	91	1 ≤ N ≤ 100	0 ≤ K ≤ 109

출력

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

입출력 예제

예제 1

입력

1 1

출력

1

예제 2

입력

2 1

출력

3
4

예제 3

입력

5 99

출력

812420891
724220653
692773316
452277443
513756160