eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Цепочка

Цепочка

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Цепочка состоит из N колец, каждое из которых покрашено в один из K цветов. Рассмотрим две такие цепочки. Для каждой из них выберем одно из крайних колец и, начиная с него, выпишем по порядку цвета всех колец, из которых она состоит. Будем считать эти цепочки одинаковыми, если в результате можно получить одинаковые последовательности цветов.

Требуется найти количество различных цепочек.

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

Во входном фйле записаны числа N и K (1N10^9, 1K10^9).

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

Выведите количество различных цепочек, состоящих из N колец, каждое из которых покрашено в один из K цветов. Если ответ превосходит 999999999, выведите девять последних цифр искомого числа.

Пример

Входные данные #1
2 1
Выходные данные #1
1
Источник III Международная Летняя школа программирования 2012 г. Севастополь