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

 

Output

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

 

Sample Input

 

Sample Output

 /**

  * code generated by JHelper

  * More info: https://github.com/AlexeyDmitriev/JHelper

  * @author xyiyy @https://github.com/xyiyy

  */

 #include <iostream>

 #include <fstream>

 //#####################

 //Author:fraud

 //Blog: http://www.cnblogs.com/fraud/

 //#####################

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include <iostream>

 #include <sstream>

 #include <ios>

 #include <iomanip>

 #include <functional>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <list>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <set>

 #include <map>

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <climits>

 #include <cctype>

 using namespace std;

 #define rep2(X, L, R) for(int X=L;X<=R;X++)

 typedef long long ll;

 int dp[][];

 int dp2[];

 const int mod = ;

 class hdu5362 {

 public:

     void solve(std::istream &in, std::ostream &out) {

         int n, m;

         in >> n >> m;

         dp[][] = ;

         rep2(i, , n) {

             for (int j = (i & ); j <= m && j <= i; j++) {

                 if (!j)dp[i][j] = dp[i - ][j + ];

                 else if (j == i || j == m)dp[i][j] = (ll) dp[i - ][j - ] * (m - j + ) % mod;

                 else dp[i][j] = ((ll) dp[i - ][j - ] * (m - j + ) + (ll) dp[i - ][j + ] * (j + )) % mod;

             }

         }

         dp2[] = ;

         rep2(i, , n) {

             dp2[i] = (ll) dp2[i - ] * m % mod;

         }

         int ans = ;

         rep2(i, , n) {

             ans = (ans + (ll) dp[i][i & ] * (n - i + ) % mod * dp2[n - i]) % mod;

         }

         out << ans << endl;

     }

 };

 int main() {

     std::ios::sync_with_stdio(false);

     std::cin.tie();

     hdu5362 solver;

     std::istream &in(std::cin);

     std::ostream &out(std::cout);

     int n;

     in >> n;

     for (int i = ; i < n; ++i) {

         solver.solve(in, out);

     }

     return ;

 }