B. Количество строк
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Для тех, кто еще не понял: этой зимой в городе XXXводске реально холодно! Настолько холодно, что в голову порой лезут странные мысли. Например, сколько существует строк длины ровно n, над алфавитом размера m, таких, что любая подстрока длины в точности k является палиндромом. Ваша задача — найти это количество по модулю 1000000007 (109 + 7). Смотрите не упустите ни одной!

Напоминаем, что подстрока является палиндромом, если она одинаково читается как слева направо, так и справа налево.

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

Первая и единственная строка содержит три целых числа: n, m и k (1 ≤ n, m, k ≤ 2000).

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

Выведите одно целое число — количество строк описанного вида по модулю 1000000007 (109 + 7).

Примеры
Входные данные
1 1 1
Выходные данные
1
Входные данные
5 2 4
Выходные данные
2
Примечание

В первом примере допустимой является только одна строка: «a» (обозначим как «a» единственную букву нашего алфавита).

Во втором примере (если обозначить буквы алфавита как «a» и «b») допустимы следующие строки: «aaaaa» и «bbbbb».