#5504. 「POI2006 R3」圆圈舞 Dancing in Circles

标签: 传统 | 时间限制: 100 ms | 内存限制: 32 MiB |

题目描述

某个幼儿园有 $n$ 个孩子，他们每天排成 $k$ 个圆圈跳舞。每个圆圈里至少有 $l$ 个孩子。如果存在某个孩子，他在两种排列方式中其右侧的邻居不同，那么我们就认为这两种排列方式是不同的。

你的任务是计算所有不同排列方式的总数，结果对 $2005$ 取模。如果没有满足所述条件的排列，则正确结果为 $0$ 。

请编写一个程序，实现以下功能：

从标准输入读取数字 $n, k$ 以及 $l$ ，
计算 $d' = d \bmod{2005}$ 的值，其中 $d$ 是孩子们所有不同排列方式的总数（ $d \bmod{2005}$ 表示 $d$ 除以 $2005$ 的余数），
将 $d'$ 输出到标准输出。

输入的第一行且仅一行包含三个由单个空格隔开的整数： $n,k,l$ $(3 \le n \le 1000000000,1 \le k \le n,2 \le l \le n)$，分别表示孩子的人数，圆圈的数量，以及每个圆圈中最少的孩子人数。

输出的第一行且仅一行应包含一个数字 $d \bmod{2005}$ 。

输入

7 2 3

输出