Картини штампами
Бессі виявила, що у неї є смуга полотна довжиною 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.