Just A String

Problem 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 \le n, m \le 2000)$.

Output

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

Sample Input

3
2 2
3 2
10 3

Sample Output

10
40
1908021

Author

zimpha@zju

Source

2015 Multi-University Training Contest 6