odd doctor 已更新

Just A String

Time Limit
3s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
50.00%(1/2)
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⋅mn mod 1000000007.

Sample Input:
3
2 2
3 2
10 3
Sample Output:
10
40
1908021
Source:

2015 Multi-University Training Contest 6


Submit