Даны два числа n и m. Посчитайте количество строк длины n, символы которых принадлежат алфавиту размера m, которые не содержат в качестве подстроки палиндромов длины больше единицы.

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

В первой строке записано целое число t - количество тестов. Далее следуют сами тесты. Каждый тест предствляет собой строку, в которой записано два целых числа n и m (1 ≤ n, m ≤ 109).

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

Для каждого теста выведите требуемое количество по модулю 109 + 7.