Счастливый конец с счастливой картиной
После того как полиция поймала Бариша, его оштрафовали.Бариш оказался обладателем полотна длиной в 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.