Анти-паліндромні рядки#9616
Дано два цілих числа і . Порахуйте кількість рядків довжини , складених із символів алфавіту потужності , які не містять жодної підрядки, що є паліндромом довжини більше одиниці.
У першому рядку задано кількість тестів . Кожний тест складається з одного рядка, що містить два цілих числа і m~(1 \le n, m \le 10^9).
Для кожного тесту виведіть шукану кількість рядків по модулю 10^9 + 7.
Приклад 1