Dancing in Circles

Time limit3sMemory limit512 MB

Summary

Count ways to split n labeled children into k unordered directed cycles of length at least l, modulo 2005.

Level: Hard8 of 10
Topics: Combinatorics, Math, Dynamic programming, Number theory
Solved: No attempts yet

Problem

A kindergarten is attended by $n$ children. Every day the children arrange themselves into $k$ circles and dance. Each circle must contain at least $l$ children.

Two arrangements are considered different if some child has a different right-hand neighbour in one arrangement than in the other. In other words, each circle is a directed ring in which every child has exactly one right neighbour, and the circles themselves are unordered.

Compute the number of distinct arrangements modulo $2005$ . If no arrangement satisfies these conditions, the answer is $0$ .

Input

The first and only line contains three integers separated by single spaces: $n$ , $k$ , and $l$ .

$n$ : the number of children ( $3 \le n \le 10^9$ )
$k$ : the number of circles ( $1 \le k \le n$ )
$l$ : the minimum number of children in each circle ( $2 \le l \le n$ )

Output

Print, on a single line, the number of distinct arrangements modulo $2005$ .

Examples3

Example 1
Input
```
7 2 3
```
Expected output
```
420
```
Example 2
Input
```
3 1 2
```
Expected output
```
2
```
Example 3
Input
```
6 3 2
```
Expected output
```
15
```