Description:

soda has a random string of length n which is generated by the following algorithm: each of n characters of the string is equiprobably chosen from the alphabet of size m.

For a string s, if we can reorder the letters in string s so as to get a palindrome, then we call s a good string.

soda wants to know the expected number of good substrings in the random string.

Input:

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integers n and m (1≤n,m≤2000).

Output:

For each case, if the expected number is E, a single integer denotes E⋅m^{n} mod 1000000007.

Sample Input:

3 2 2 3 2 10 3

Sample Output:

10 40 1908021

Source:

Submit