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

见题面

见题面