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.
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
).
For each test case print in a separate line the required number of strings taken by modulo 10^9
+ 7.