P1357 Garden

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$.

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

Output one line with a single integer, the answer.

#### 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