1 /**
 2  * code generated by JHelper
 3  * More info: https://github.com/AlexeyDmitriev/JHelper
 4  * @author xyiyy @https://github.com/xyiyy
 5  */
 6 
 7 #include <iostream>
 8 #include <fstream>
 9 
10 //#####################
11 //Author:fraud
12 //Blog: http://www.cnblogs.com/fraud/
13 //#####################
14 //#pragma comment(linker, "/STACK:102400000,102400000")
15 #include <iostream>
16 #include <sstream>
17 #include <ios>
18 #include <iomanip>
19 #include <functional>
20 #include <algorithm>
21 #include <vector>
22 #include <string>
23 #include <list>
24 #include <queue>
25 #include <deque>
26 #include <stack>
27 #include <set>
28 #include <map>
29 #include <cstdio>
30 #include <cstdlib>
31 #include <cmath>
32 #include <cstring>
33 #include <climits>
34 #include <cctype>
35 
36 using namespace std;
37 #define rep2(X, L, R) for(int X=L;X<=R;X++)
38 typedef long long ll;
39 
40 int dp[2010][2010];
41 int dp2[2010];
42 const int mod = 1000000007;
43 
44 class hdu5362 {
45 public:
46     void solve(std::istream &in, std::ostream &out) {
47         int n, m;
48         in >> n >> m;
49         dp[0][0] = 1;
50         rep2(i, 1, n) {
51             for (int j = (i & 1); j <= m && j <= i; j++) {
52                 if (!j)dp[i][j] = dp[i - 1][j + 1];
53                 else if (j == i || j == m)dp[i][j] = (ll) dp[i - 1][j - 1] * (m - j + 1) % mod;
54                 else dp[i][j] = ((ll) dp[i - 1][j - 1] * (m - j + 1) + (ll) dp[i - 1][j + 1] * (j + 1)) % mod;
55             }
56         }
57         dp2[0] = 1;
58         rep2(i, 1, n) {
59             dp2[i] = (ll) dp2[i - 1] * m % mod;
60         }
61         int ans = 0;
62         rep2(i, 1, n) {
63             ans = (ans + (ll) dp[i][i & 1] * (n - i + 1) % mod * dp2[n - i]) % mod;
64         }
65         out << ans << endl;
66     }
67 };
68 
69 int main() {
70     std::ios::sync_with_stdio(false);
71     std::cin.tie(0);
72     hdu5362 solver;
73     std::istream &in(std::cin);
74     std::ostream &out(std::cout);
75     int n;
76     in >> n;
77     for (int i = 0; i < n; ++i) {
78         solver.solve(in, out);
79     }
80 
81     return 0;
82 }