406105: GYM102267 J Zoo

The mayor built a new Zoo. The Zoo looks like a cycle made up of $$$n$$$ animal viewing locations, the locations are numbered from $$$1$$$ to $$$n$$$ where locations $$$i$$$ and $$$i+1$$$ are adjacent and locations $$$1$$$ and $$$n$$$ are also adjacent. Before entering the Zoo, citizens pick two locations $$$a$$$, $$$b$$$ such that $$$(a \neq b)$$$, and one of the two simple paths connecting them(clockwise or counter clockwise) such that the distance between $$$a$$$ and $$$b$$$ is at most $$$k$$$ along that path.

The citizens then starts walking between the locations following 4 conditions:

1) The citizens shouldn't move outside the path between $$$a$$$ and $$$b$$$.

2) All locations between $$$a$$$ and $$$b$$$ along the chosen path should be visited.

3) The walk should end on the starting location $$$a$$$.

4) The length of the walk is at most $$$m$$$.

How many possible walks can the citizens make? print that number module $$$10^9+7$$$.

The input is made up of one line containing $$$3$$$ integers $$$n$$$, $$$k$$$, $$$m$$$, $$$(1 \leq k < n \leq 10^5, 1 \leq m \leq 2000)$$$.

Print one integer $$$x$$$ the answer to the problem module $$$10^9+7$$$.

4 3 3

8

10 5 6

160