#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;
}