Competitions
Азербайджан - подготовка. Март 12
Anti-palindromic strings
Two integers n and m are given. Find the number of strings of length n, which symbols belong to the alphabet of size m, that do not contain palindromes of length more than one as substrings.
Input data
First line contains the number of test cases t. Each test is a separate line with two integers n and m (1 ≤ n, m ≤ 10^9).
Output data
For each test case print in a separate line the required number of strings taken by modulo 10^9 + 7.
Examples
Input example #1
2 5 6 6 5
Output example #1
1920 1620
Input example #2
4 3 6 1 3 3 1 2 4
Output example #2
120 3 0 12