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