Description

Xiao L has a circular garden. Number the flower plots from $1$ to $n$ in the clockwise direction. Plots $1$ and $n$ are adjacent.

His circular garden can have a new arrangement every day, but all arrangements must follow one rule: in any $m$ consecutive plots, there are at most $k$ plots of type "C", and all remaining plots are of type "P".

For example, if $n = 10$, $m = 5$, $k = 3$, then:

• CCPCPPPPCC is an arrangement that does not satisfy the rule.
• CCPPPPCPCP is an arrangement that satisfies the rule.

Please compute the number of arrangements that satisfy the rule, modulo $10^9 + 7$.

Input Format

One line containing three integers $n$, $m$, and $k$.

Output Format

Output one line with a single integer, the answer.

10 5 3

458

6 2 1

18

Hint

Constraints

• For $40\%$ of the testdata, $n \le 20$.
• For $60\%$ of the testdata, $m = 2$.
• For $80\%$ of the testdata, $n \le 10^5$.
• For $100\%$ of the testdata, $2 \le n \le 10^{15}$, $2 \le m \le \min(n, 5)$, $1 \le k \lt m$.

Translated by ChatGPT 5