Шырдак


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Шырдак — кыргызский войлочный ковёр с мозаичным орнаментом. В 2012 году искусство шырдака внесено ЮНЕСКО в список нематериального культурного наследия, нуждающегося в срочной охране.

Мастерица Айпери из Нарына делает круглые шырдаки. Кайма такого ковра — кольцо из n одинаковых войлочных секторов, расположенных по кругу. Каждый сектор окрашивается в один из k цветов, при этом по традиции соседние секторы должны быть разного цвета (сектор n тоже соседствует с сектором 1).

Ковёр можно повернуть, поэтому две раскраски каймы считаются одинаковыми, если одна получается из другой поворотом кольца. Отражать ковёр нельзя: у него есть лицевая и изнаночная стороны.

Сколько существует различных кайм? Так как ответ может быть очень большим, выведите его остаток от деления на 10⁹ + 7.

Рисунок

Входные данные

В первой строке — целое число T (1 ≤ T ≤ 100) — количество вопросов.

В каждой из следующих T строк — два целых числа n и k (3 ≤ n ≤ 10¹⁸, 1 ≤ k ≤ 10¹⁸).

Выходные данные

Для каждого вопроса выведите в отдельной строке количество различных кайм по модулю 10⁹ + 7.

Пример 1

Вход:

3
3 3
4 2
6 3

Выход:

2
1
14

Пояснение

При n = 3 и k = 3 все три сектора разного цвета; шесть таких раскрасок разбиваются на две группы по три поворота. При n = 4 и k = 2 подходят только чередующиеся раскраски, и обе совпадают при повороте на один сектор.

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 10 n ≤ 9, k ≤ 4
2 20 n ≤ 100, либо n — простое число, либо n — степень простого числа (возможно, умноженная на 10⁹ + 7)
3 30 n не делится на 10⁹ + 7
4 40 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.

Примечание

Обратите внимание, что n может делиться на 10⁹ + 7.


Комментарии

Еще нет ни одного комментария.