#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #define MOD 1000000007 using namespace std; int main() { int t; cin>>t; while(t--) { int n, k; cin>>n>>k; long long int passes = n, players = k; long long int m = 0; long long int a[passes], b[passes]; memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); a[1] = 0; b[1] = players; for(long long int i=1; i<=passes+1; i++) { a[i+1] = b[i]; b[i+1] = (((players%MOD)*(a[i]%MOD))%MOD + ((players-1)%MOD*(b[i]%MOD))%MOD)%MOD; } cout<<a[passes]<<endl; } return 0; }