eolymp
Yarışlar

2018 USACO January

Картины штампами

Бесси обнаружила, что у нее имеется полоса холста длины n, и она намеревается закрасить ее. Однако у нее не было возможности приобрести кисти для рисования. Вместо них у нее имеются m резиновых штампов разных цветов, каждый штамп k единиц шириной. Пораженная открывающимися перед ней возможностями, она хочет точно знать, сколько разных картин она могла бы создать, штампуя свои штампы в определенном порядке на холсте.

Чтобы использовать штамп, сначала необходимо найти ровно k соседних единиц на холсте. Штамп не может выходить за края холста и закрывать часть единиц. После размещения штамп закрашивает k единиц своим цветом. Любой штамп можно использовать несколько раз, один раз или даже никогда. Но к тому времени, когда Бесси закончит, каждая единица холста должна быть закрашена хотя бы один раз.

Помогите Бесси найти количество различных картин, которые она могла бы нарисовать, по модулю 109 + 7. Две картины, которые выглядят одинаково, но были написаны в разной последовательности операций штамповки, считаются одинаковыми.

Входные данные

Одна строка содержит три целых числа n (1n106), m (1m106) и k (1k106). Гарантируется, что kn.

Выходные данные

Выведите количество возможных картин по модулю 109 + 7.

Пример

Если два штампа имеют цвета A и B, то возможными картинами будут AAA, AAB, ABB, BAA, BBA и BBB.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3 2 2
Çıxış verilənləri #1
6
Mənbə 2018 USACO Январь, Золото