题目描述

$n$ kids attend a certain kindergarten. Everyday the kids arrange themselves in $k$ circles and dance.

At least $l$ kids dance in each circle. Two arrangements of children are considered distinct if there isa child who has a different right neighbour in one of the arrangements than in the other.

Your task is to calculate the number of all distinct arrangements modulo $2005$. Should there beno arrangements satisfying the aforementioned conditions, the correct outcome is $0$.

TaskWrite a programme which:

reads the numbers $n$, $k$ and $l$ from the standard input, calculates the number $d'=d\ mod\ 2005$, where $d$ denotes the number of distinct arrangements of the children ($d\ mod\ 2005$ denotes the remainder of the division of $d$ by $2005$), writes $d'$ to the standard output.

幼儿园中有N个小朋友在做游戏，每天小朋友们都会有一个尬舞方案（围成K个圈尬舞）。

每个圈子里至少有L个小朋友，如果在一个方案里有一个小朋友他右面的小朋友和另一个方案里他右面的小朋友不同，那么两个尬舞方案就会被认为是不同的。

你的任务是计算所有不同的尬舞方案的数量，因为结果可能比较大，所以最后输出答案mod2005的结果。

如果没有符合要求的尬舞方案，输出0。

输入格式

The first and only line of the standard input contains three integers separated by single spaces: $n$- the number of children ($3\le n\le 1\ 000\ 000\ 000$), $k$ - the number of circles($1\le k\le n$) and $l$ - the minimal number of kids in a circle ($2\le l\le n$).

只有一行输入，三个整数N,K,L(3≤N≤1,000,000,000 ; 1≤K≤n ; 2≤L≤n)分别代表小朋友数量，圈子数量，每个圈子里最少的小朋友数。

输出格式

The first and only line of the standard output should contain a single integer: $d\ mod\ 2005$.

只有一行输出，即合理的尬舞方案数d(mod2005)

7 2 3

420

提示

感谢@Paperback_Writer 提供翻译