Ланцюжок#3675
Ланцюжок складається з кілець, кожне з яких пофарбоване в один з кольорів. Розглянемо два такі ланцюжки. Для кожного з них виберемо одне з крайніх кілець і, починаючи з нього, випишемо по порядку кольори всіх кілець, з яких він складається. Вважатимемо ці ланцюжки однаковими, якщо в результаті можна отримати однакові послідовності кольорів.
Потрібно знайти кількість різних ланцюжків.
У вхідному файлі записані числа і (1 \le N \le 10^9, 1 \le K \le 10^9).
Виведіть кількість різних ланцюжків, що складаються з кілець, кожне з яких пофарбоване в один з кольорів. Якщо відповідь перевищує , виведіть дев'ять останніх цифр шуканого числа.
Приклад 1