Ланцюжок

Цепочка складається з N кілець, кожне з яких пофарбоване в один з K кольорів. Розглянемо дві такі цепочки. Для кожної з них виберемо одне з крайніх кілець і, починаючи з нього, випишемо по порядку кольори всіх кілець, з яких вона складається. Вважатимемо ці цепочки однаковими, якщо в результаті можна отримати однакові послідовності кольорів.

Потрібно знайти кількість різних цепочок.

Вхідні дані

У вхідному файлі записані числа N і K (1 ≤ N ≤ 10^9, 1 ≤ K ≤ 10^9).

Вихідні дані

Виведіть кількість різних цепочок, що складаються з N кілець, кожне з яких пофарбоване в один з K кольорів. Якщо відповідь перевищує 999999999, виведіть дев'ять останніх цифр шуканого числа.

Приклади