Just A String

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≤n,m≤2000).

For each case, if the expected number is E, a single integer denotes E⋅mⁿ mod 1000000007.

3
2 2
3 2
10 3

10
40
1908021

2015 Multi-University Training Contest 6