Щасливий кінець зі щасливим малюнком
Після того, як поліція зловила Бариша, його оштрафували. Бариш опинився у володінні полотна довжиною N одиниць ( 1 ≤ N ≤ 10^6), і він має намір його розмалювати. Однак, він не зміг дістати пензлі. Замість них у нього є M гумових штампів різних кольорів (1 ≤ M ≤ 10^6 ), кожен штамп шириною K одиниць (1 ≤ K ≤ 10^6 ). Вражений можливостями, що перед ним відкриваються, він хоче знати, скільки різних картин він міг би створити, штампуючи свої штампи в певному порядку на полотні. Щоб використати штамп, його потрібно вирівняти точно з K сусідніми одиницями на полотні. Штамп не може виходити за межі полотна і не може покривати частини одиниць. Після розміщення штамп зафарбовує K покритих одиниць своїм кольором. Будь-який даний штамп може бути використаний кілька разів, один раз або навіть жодного разу. Але до того часу, як Бариш закінчить, кожна одиниця полотна має бути зафарбована принаймні один раз. Допоможіть Баришу знайти кількість різних картин, які він міг би намалювати, за модулем 10^9+7. Дві картини, які виглядають однаково, але були намальовані різними послідовностями штампування, вважаються однаковими.
Вхідні дані
Числа N, M, K подані в першому рядку. K ≤ N .
Формат виходу:
Одне ціле число: кількість можливих картин, за модулем 10^9 + 7.
Пояснення до першого тестового випадку
Якщо два штампи мають кольори A і B, можливі картини: AAA, AAB, ABB, BAA, BBA, і BBB.