Sumo was travelling alone at night, suddenly he saw a spaceship and out of it came an alien named KK. Obviously, the alien had a different language and thus couldn't communicate readily. After some psycho-telepathic talk, Sumo realised that KK's language has M distinct characters. And a valid word in his language satisfies the following properties:

 Each character in the word must be one of the M characters. 
There must be no  palindromic substring of size greater than 1.



For some reason Sumo wants to know the number of valid words of length N in KK's language. Since the answer can be large, print the answer modulo 1000000007 (10^9 + 7).
 

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space separated integers N and  M  as described in the problem statement.


Output

For each test case, output a single line containing the answer to the corresponding test case. See example section for better understanding.


Constraints

1 ≤ T ≤ 100000
1 ≤ N ≤ 1000000000
1 ≤ M ≤ 1000000000


Example
Input:
2
3 3
1 4

Output:
6
4
#Anwesh Mohanty
mod=10**9+7
t=input()
while t>0:
	n,m=map(int,raw_input().split())
	if n==1:
		print m%mod
	elif n==2:
		print m*(m-1)
	else:
		print (m*(m-1)*pow(m-2,n-2,mod)%mod) #nPm
	t-=1