Slave to Achievements 3

No attempts yetTime limit3sMemory limit256 MB

Problem

Kyeonggeun has been playing a web game called isRPG. As the RPG in the name suggests, the game has a lot of equipment items a character can use. Every item is built by gathering materials the way the recipe says, and the options on a finished item are drawn at random from a fixed range. If a finished item is not to his liking, he can dismantle it and get part of the spent materials back.

isRPG has an achievement system, the way most recent games do, so reaching a set number on some counter earns an achievement. The counters Kyeonggeun cares about right now are "craft this many items of equipment" and "dismantle this many items of equipment".

The easiest item to craft in isRPG is the wooden dagger. Its only material is the wood scrap, and the shop sells wood scraps cheaply. The quality of the item has nothing to do with the achievements, so Kyeonggeun decided to carve wooden daggers by the pile.

Spending NN wood scraps produces one wooden dagger. Dismantling one wooden dagger returns anywhere from 00 to KK wood scraps. The probability of getting exactly xx (0xK0 \le x \le K) scraps back does not depend on the value of xx: it is 1/(K+1)1/(K+1) for every xx.

After killing a pile of treasure-hoarding dragons and collecting the loot, Kyeonggeun bought MM wood scraps at the shop. He holds no wooden dagger at the moment. From now on he repeats this work: craft wooden daggers from the scraps he holds until he cannot craft a single one more, then dismantle every wooden dagger he holds. Long experience has taught Kyeonggeun that wood scraps sitting in the inventory once all the work is over feel very unpleasant. So he wants to know the probability that 0 wood scraps are left when all the work is over. Having thought that far, he also became curious about the probability that ii (0i<N0 \le i < N) scraps are left. Help him out.

Input

The first line has NN, KK and MM, separated by spaces. NN is the number of wood scraps one wooden dagger costs, and KK is the largest number of wood scraps one dismantled wooden dagger returns. (1K<N1031 \le K < N \le 10^3)

MM is the number of wood scraps Kyeonggeun starts with. It either satisfies 0M10120 \le M \le 10^{12} or equals 1-1. The value M=1M = -1 means the answer is the limit each probability converges to as the starting number of wood scraps goes to infinity. The limit exists and is rational, and that has been proven.

Output

On line ii, print the probability that i1i-1 wood scraps are left. At most N1N-1 scraps are ever left, so the output has exactly NN lines.

For an exact check, write the probability as a reduced fraction pq\frac{p}{q} and print the integer rr with 0r<109+70 \le r < 10^9+7 that satisfies pqr0(mod109+7)p - qr \equiv 0 \pmod{10^9+7}. Such an integer rr exists and is unique in that range, and that has been proven.

Hint

In the example with N=4N = 4, K=2K = 2, M=4M = 4, the printed values mean 13\frac{1}{3}, 13\frac{1}{3}, 13\frac{1}{3}, 00 in that order. In the example with the same NN and KK and M=1M = -1, they mean 19\frac{1}{9}, 29\frac{2}{9}, 13\frac{1}{3}, 13\frac{1}{3} in that order.