Цепочка
Ограничение по времени выполнения 1 секунда
Ограничение по использованию памяти 256 мегабайт
Цепочка состоит из N колец, каждое из которых покрашено в один из K цветов. Рассмотрим две такие цепочки. Для каждой из них выберем одно из крайних колец и, начиная с него, выпишем по порядку цвета всех колец, из которых она состоит. Будем считать эти цепочки одинаковыми, если в результате можно получить одинаковые последовательности цветов.
Требуется найти количество различных цепочек.
Входные данные
Во входном фйле записаны числа N и K (1 ≤ N ≤ 10^9, 1 ≤ K ≤ 10^9).
Выходные данные
Выведите количество различных цепочек, состоящих из N колец, каждое из которых покрашено в один из K цветов. Если ответ превосходит 999999999, выведите девять последних цифр искомого числа.
Примеры
Ввод #1
Ответ #1
Отправки 21
Коэффициент принятия 24 %