Картины штампами
Бесси обнаружила, что у нее имеется полоса холста длины n, и она намеревается закрасить ее. Однако у нее не было возможности приобрести кисти для рисования. Вместо них у нее имеются m резиновых штампов разных цветов, каждый штамп k единиц шириной. Пораженная открывающимися перед ней возможностями, она хочет точно знать, сколько разных картин она могла бы создать, штампуя свои штампы в определенном порядке на холсте.
Чтобы использовать штамп, сначала необходимо найти ровно k соседних единиц на холсте. Штамп не может выходить за края холста и закрывать часть единиц. После размещения штамп закрашивает k единиц своим цветом. Любой штамп можно использовать несколько раз, один раз или даже никогда. Но к тому времени, когда Бесси закончит, каждая единица холста должна быть закрашена хотя бы один раз.
Помогите Бесси найти количество различных картин, которые она могла бы нарисовать, по модулю 10^9 + 7. Две картины, которые выглядят одинаково, но были написаны в разной последовательности операций штамповки, считаются одинаковыми.
Входные данные
Одна строка содержит три целых числа n (1 ≤ n ≤ 10^6), m (1 ≤ m ≤ 10^6) и k (1 ≤ k ≤ 10^6). Гарантируется, что k ≤ n.
Выходные данные
Выведите количество возможных картин по модулю 10^9 + 7.
Пример
Если два штампа имеют цвета A и B, то возможными картинами будут AAA, AAB, ABB, BAA, BBA и BBB.