#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
	ll k;
	cin >> k;
	ll x, y, p, q;
	cin >> x >> y >> p >> q;
	if(x == p && y == q) {
		cout << 0 << endl;
		return 0;
	}
	if(abs(x - p) + abs(y - q) <= k || x - y == p - q || (x + y) == (p + q)) {
		cout << 1 << endl;
		return 0;
	} 
	ll xx = (y + x) & 1;
	ll yy = (q + p) & 1;
	if(xx != yy && abs(x - p) + abs(y - q) > 2 * k && abs((p - x) - (q - y)) > k && abs((x + y) - (q + p)) > k) {
		cout << 3 << endl;
	}  else {
		cout << 2 << endl;
	}
}

B

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MODE = 1e9 + 7;
ll n, k;
ll qpower(ll a, ll b) {
	ll ans = 1;
	while(b) {
		if(b & 1) {
			ans = (ans * a) % MODE;
		}
		a = (a * a) % MODE;
		b >>= 1;
	}
	return ans;
}
int main () {
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> k;
		ll  x = ((k - 1) + (k - 2) * (k - 2) % MODE) % MODE;
		ll ans = (((qpower(x, n - 1) * k) % MODE) * (k - 1)) % MODE;
		cout << ans << endl;
	}
}