408913: GYM103379 I Santa's Last Journey

Santa is tired after a long night delivering presents, and has reached his final stop, Rayville.

As its name suggests, Rayville is built as a ray on the $$$x$$$-axis, from $$$0$$$ to $$$\infty$$$. Each unit length integer interval containts a house (e.g. $$$[0,1),[1,2), [2,3), \dots$$$), and on each integer coordinate there is a light pole (e.g. at points $$$(0,0), (1,0), (2,0), \dots$$$)

Santa moves along the ray from $$$0$$$ to $$$\infty$$$. Each time he reaches a light pole (excluding light pole 0), with probability $$$1/z$$$, he collapses, never to move again.

Initially, all the light poles are off. Each time Santa reaches light pole $$$i > 0$$$ (even if he collapses at it), he bumps into it, causing the fragile lighting system of Rayville to flicker, turning light pole $$$i$$$ to turn on with probability $$$\min(1, l/i)$$$. If this causes $$$> l$$$ lightpoles to be on it overloads Rayville's electrical grid, causing one of the prior lights $$$< i$$$ to go out (uniformly, at random).

When Santa collapses, he takes joy from two things: one is the set of light poles that are on. More specifically, if a light pole $$$i$$$ is on, then Santa gets $$$i$$$ units of lights joy, and the total lights joy Santa gets is the sum of all the joys from light poles.

The other is the number of ways he could have delivered exactly $$$m$$$ presents to the houses he has passed, call this Santa's presents joy. (Two ways are considered different iff there is some house that gets a different number of presents in each way).

Santas total joy is the product of the above two sources, that is lights joy * presents joy.

What is Santa's expected total joy? Output your answer $$$\mod 10^9 + 7$$$.

One line containing 3 space separated integers, $$$l$$$, $$$m$$$, $$$z$$$, ($$$1\leq l,m \leq 10^6$$$), ($$$1\leq z \leq 10^9$$$). $$$l$$$ is the max number of lightpoles that can be on, $$$m$$$ is the number of presents Santa must deliver, and $$$1/z$$$ is the probability Santa dies at any light pole.

Santa's expected total joy$$$\mod 10^9 + 7$$$.

1 1 2

4