Анти паліндромні рядки

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

Вхідні дані

У першому рядку задано ціле число t - кількість тестів. Далі йдуть самі тести. Кожен тест складається з одного рядка, в якому записані два цілі числа n і m (1 ≤ n, m ≤ 10^9).

Вихідні дані

Для кожного тесту виведіть потрібну кількість за модулем 10^9 + 7.

Приклади