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

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)이 공백을 사이로 두고 주어진다.</p>

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

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>

좀더 정확하게 판별하기 위해, 확률을 기약분수로 ( {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 )을 의미한다.