Шырдак
Шырдак — кыргызский войлочный ковёр с мозаичным орнаментом. В 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.
Комментарии