У Беси есть полоса холста длиной \(N\) единиц(\(1 \leq N \leq 10^6\)), которую она
собирается раскрасить. У неё есть \(M\) резиновых штампов различных цветов
(\(1 \leq M \leq 10^6\)), каждый штамп имеет \(K\) в ширину (\(1 \leq K \leq 10^6\)).
Она хочет точно узнать, сколько различных рисунков она может создать, используя
свои штампы в некотором порядке.
Чтобы использовать штамп, он должен занять ровно \(K\) соседних единиц холста.
Штамп не может выходить за концы холста, и не может покрывать часть единицы.
Однажды размещённый, штамп закрашивает \(K\) покрытых единиц своим цветом. Любой
штамп может быть использован множество раз, один раз или даже не использован
ни разу. Но к моменту завершения работы Беси, каждая единица холста должна быть
закрашена как минимум один раз.
Помогите Беси оперделить количество различных рисунков, которые она может
нарисовать по модулю \(10^9 + 7\). Два рисунка, которые выглядят идентично, но
были нарисованы различными штамповыми операциями, засчитываются как один и тот
же рисунок.
Как минимум в 75% тестов, \(N,K \leq 10^3\).
ФОРМАТ ВВОДА (файл spainting.in):
Первая строка ввода содержит три целых числа \(N\), \(M\), \(K\). Гарантируется,
что \(K \leq N\).
ФОРМАТ ВЫВОДА (файл spainting.out):
Одно целое число, количество различных раскрашиваний по модулю \(10^9 + 7\).
Ваш ответ: