Задачи
Анти палиндромные строки
Анти палиндромные строки
Даны два числа n и m. Посчитайте количество строк длины n, символы которых принадлежат алфавиту размера m, которые не содержат в качестве подстроки палиндромов длины больше единицы.
Входные данные
В первой строке записано целое число t - количество тестов. Далее следуют сами тесты. Каждый тест предствляет собой строку, в которой записано два целых числа n и m (1 ≤ n, m ≤ 109
).
Выходные данные
Для каждого теста выведите требуемое количество по модулю 109
+ 7.
Входные данные #1
2 5 6 6 5
Выходные данные #1
1920 1620
Входные данные #2
4 3 6 1 3 3 1 2 4
Выходные данные #2
120 3 0 12