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.
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)$.
For each case, if the expected number is $E$, a single integer denotes $E \cdot m^n \text{ mod } 1000000007$.