Равномерные раскраски
(Время: 1 сек. Память: 32 Мб Сложность: 24%)
Вершины правильного N-угольника занумерованы последовательными целыми числами от 1 до N, а каждая из его сторон окрашена в один из K цветов.
Назовём раскраску многоугольника равномерной, если любые K подряд идущих сторон окрашены в попарно различные цвета. По заданным N и K найдите количество различных равномерных раскрасок. Две раскраски считаются различными, если в этих раскрасках хотя бы для одной пары смежных вершин a и b сторона, которая соединяет эти вершины, окрашена в разные цвета.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и K (K ≤ N ≤109, 1 ≤ K ≤ 12).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число — количество различных равномерных раскрасок правильного N-угольника в
K цветов.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 2 | 0 |
| 2 | 115 5 | 120 |
| 3 | 3 3 | 6 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
