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$.

3
2 2
3 2
10 3

10
40
1908021

Author

zimpha@zju