Даны два числа n и m. Посчитайте количество строк длины n, символы которых принадлежат алфавиту размера m, которые не содержат в качестве подстроки палиндромов длины больше единицы.
В первой строке записано целое число t - количество тестов. Далее следуют сами тесты. Каждый тест предствляет собой строку, в которой записано два целых числа n и m (1 ≤ n, m ≤ 10^9
).
Для каждого теста выведите требуемое количество по модулю 10^9
+ 7.