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