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

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

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

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

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

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

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

Пример

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