虽然$O(N*ai*logbi)$ 最糟糕有$O(100*10^9*log10^9)=O(9*10^11)$会超，但是迫切想解决 MLE 的问题

#include <bits/stdc++.h>
#define mod_ 10000
using namespace std;

long long Counting(long long a, long long b) {
	long long r = 1;
	while (b) {
		if (b & 1 == 1)
			r = r * a % mod_;
		a = a * a % mod_;
		b = b >> 1;
	}
	return r % mod_;
}

long long f(long long a, long long b) {
	if (a == 1)
		return 1;
	return (Counting(a, b) % mod_ + f(a - 1, b) % mod_) % mod_;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		int a, b;
		cin >> a >> b;
		cout << f(a, b);
		puts("");
	}
	return 0;
}