시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 20 8 6 33.333%

문제

경근이는 요즘 isRPG라는 웹게임을 열심히 하고 있다. 제목에 RPG가 들어가 있으니 알 수 있겠지만, 이 게임에는 캐릭터가 사용할 수 있는 많은 장비 아이템들이 있다. 모든 장비는 주어진 방법을 따라 재료를 모아 만들고, 만들어진 장비의 옵션은 정해진 범위 내에서 무작위하게 결정된다. 만약 만들어진 장비가 마음에 들지 않는다면 장비를 해체하여 사용한 재료를 일부분 돌려받을 수 있다.

isRPG에는 요즈음의 많은 게임이 그러하듯 업적이라는 시스템이 있어서 어떤 항목에 대해 일정 수치를 달성하게 되면 업적을 달성할 수 있다. 경근이가 현재 관심 있어 하는 항목은 "특정 개수 이상의 장비 제작하기"와 "특정 개수 이상의 장비 분해하기"이다.

현재 isRPG에서 가장 쉽게 제작할 수 있는 아이템의 최고봉은 나무 단검이다. 나무 단검의 재료는 나무 쪼가리 한 종류뿐이며, 이는 상점에서 쉽게 구매할 수 있기 때문이다. 업적을 달성하는 것과 제작하는 아이템의 질은 아무런 상관이 없으므로 경근이는 나무 단검을 많이많이 깎으려고 한다!

나무 쪼가리 \(N\)개를 소모하면 나무 단검 하나를 제작할 수 있다. 나무 단검 하나를 분해하면 나무 쪼가리를 적으면 \(0\)개, 많으면 \(K\)개까지 돌려받을 수 있다. 이 때 나무 쪼가리를 \(x\) (\(0 \leq x \leq K\))개 돌려받을 확률은, \(x\)의 값과 상관 없이, 모든 \(x\)에 대해 \(1/(K+1)\)이다.

보물을 가진 용들을 많이많이 죽여서 많은 전리품을 얻은 경근이는 상점에서 나무 쪼가리를 \(M\)개 구입했다. 현재 경근이는 나무 단검을 하나도 가지고 있지 않다. 경근이는 이제부터 나무 쪼가리로 나무 단검을 하나도 만들 수 없을 때까지 제작하고, 가지고 있는 나무 단검을 모두 분해하는 작업을 반복하려고 한다. 경근이는 수많은 경험을 통해, 모든 작업이 끝난 후에 나무 쪼가리가 인벤토리 창에 남아 있는 것은 매우 불쾌한 일이라는 것을 잘 알고 있다. 그러므로 경근이는 모든 작업이 끝난 후 나무 쪼가리가 0개 남을 확률이 얼마인지 알고 싶어 한다. 이런 생각을 하고 나니 더 나아가 나무쪼가리가 \(i\) (\(0 \leq i < N\))개 남을 확률도 알고 싶어졌다. 경근이를 도와주자!

입력

첫 번째 줄에 나무 단검 하나를 만드는 데 필요한 나무 쪼가리의 개수 \(N\), 나무 단검 하나를 분해했을 때 얻을 수 있는 나무 쪼가리의 최대 개수 \(K\) (\( 1 \leq K < N \leq 10^3\)), 현재 경근이가 가지고 있는 나무 쪼가리의 개수 \(M\)이 공백을 사이로 두고 주어진다.

이 문제는 세 개의 부분 문제로 이루어져 있다.

1번 문제의 입력은 \(0 \leq M \leq 10^{6}\)을 만족하며 해결하면 10점을 얻을 수 있다.

2번 문제의 입력은 \(0 \leq M \leq 10^{12}\)을 만족하며 해결하면 40점을 얻을 수 있다.

3번 문제의 입력은 \(M = -1\)을 만족하며 해결하면 50점을 얻을 수 있다. 이 부분 문제는 앞의 문제와는 다르게 \(M = -1\)인데, 이는 \(M\)이 무한대로 수렴할 때의 확률의 극한값을 정답으로 구해야 함을 의미한다. 이 극한값이 존재하며 유리수라는 사실은 증명되어 있다.

출력

\(i\)번째 줄에는 나무 쪼가리가 \(i-1\)개 남을 확률을 출력한다. 나무 쪼가리는 \(N-1\)개 이하만큼 남게 될 것이므로, 출력은 \(N\)줄이어야 한다.

좀더 정확하게 판별하기 위해, 확률을 기약분수로 \( {p}\over{q} \)로 나타냈을 때, \(p-qr \equiv 0 \pmod{1,000,000,007} \)을 만족하는 \(0\) 이상 \(1,000,000,007\) 미만의 정수 \(r\)을 출력해야 한다. 이 정수 \(r\)이 존재하며, 이 범위 내에서 유일하다는 사실은 증명되어 있다.

예제 입력

4 2 4

예제 출력

333333336
333333336
333333336
0

힌트

순서대로 \( \frac{1}{3} \),\( \frac{1}{3} \),\( \frac{1}{3} \),\( 0 \)을 의미한다.

출처

Contest > Coder's High > Coder's High 2015 Side Contest G2번