$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 is a 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 be no arrangements satisfying the aforementioned conditions, the correct outcome is 0.

Write a programme which:

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

Input

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

Output

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

Example

Input

7 2 3

Output

420