e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Exponentiation

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

First line contains the number of test cases t. Each test is a separate line with two integers n and m (1n, m109).

Output

For each test case print in a separate line the required number of strings taken by modulo 109 + 7.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2
5 6
6 5
Output example #1
1920
1620