Circular Garden Arrangement

Little L has a circular garden with n flowerbeds numbered from 1 to n in clockwise order. Note that the 1^st and the n^th flowerbed are adjacent. Each day, he arranges his garden into a pattern consisting of two types of flowerbeds: C‐shaped and P‐shaped. However, the arrangement must obey the following rule:

For every contiguous block of m flowerbeds (taken along the circle), there are at most k C‐shaped flowerbeds; the remaining ones are P‐shaped.

In other words, if we represent an arrangement as a circular string of length n consisting of characters C and P, then for every index i (with indices taken modulo n) the following constraint must hold: $$ \sum_{j=0}^{m-1} [s_{(i+j)\bmod n} = C] \le k, $$ where \([\cdot]\) is the indicator function.

Your task is to compute the number of valid garden arrangements modulo \(10^9+7\).

Example: When n=10, m=5, and k=3, the arrangement CCPCPPPPCC is invalid, while CCPPPPCPCP is valid.

inputFormat

The input consists of a single line containing three positive integers n, m, and k separated by spaces.

For example:

10 5 3

outputFormat

Output a single integer representing the number of valid arrangements of the garden modulo \(10^9+7\).

sample

3 2 1

4