# ZeroJudge - f729: 大數冪
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=f729
###### tags: `ZeroJudge` `數學` `數論` `質數`

#include <iostream>
#include <string>
using namespace std;
#define MOD 1000000007

const int fermatMod = MOD - 1;

int FastPower(int base, int power) {
	if (base < 2)
		return base;
	int answer = 1, buffer = base % MOD;
	while (power) {
		if (power & 1)
			answer = ((long long)answer * buffer) % MOD;
		buffer = ((long long)buffer * buffer) % MOD;
		power >>= 1;
	}
	return answer;
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	int base, times, base10Power;
	string base8Power;
	cin >> times;
	while (times--) {
		cin >> base >> base8Power; base10Power = 0;
		for (int i = 0; i != base8Power.size(); ++i)
			base10Power = (((long long)base10Power << 3) + base8Power[i] - '0') % fermatMod;
		cout << FastPower(base, base10Power) << '\n';
	}
}