eolymp
bolt
Try our new interface for solving problems
Məsələlər

Цепочка

Цепочка

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2 1
Çıxış verilənləri #1
1
Mənbə III International Summer School Programming in Sevastopol 2012