#define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; templateinline void chmin(A &a, B b) { if (a > b)a = b; } templateinline void chmax(A &a, B b) { if (a < b)a = b; } template class kitamasa_hou { int K; vectorA, D; vectoradvance(vectorx) { rotate(x.begin(), x.end() - 1, x.end()); for (int i = 1; iadvance2(vectorx) { vectory = x, z(K, 0); for (int i = 0; iA, vectorD) :K(K), A(A.begin(), A.end()), D(D.begin(), D.end()) {} ll query(ll N) { assert(K); vectorx = D; if (N> p; p++)if ((N >> p) == n)return; x = advance(x); } }(); for (p--; p >= 0; p--) { x = advance2(x); if (N >> p & 1)x = advance(x); } ll ret = 0; for (int i = 0; i>= 1; } return ret; } int main() { ll ans = 1; int N; scanf("%d", &N); kitamasa_houfib(2, { 1,2 }, { 1,1 }); for (int i = 0; i < N;i++) { ll C; char D[210]; scanf("%lld%s", &C, D); ll d = 0; for (int j = 0; D[j]; j++)d = (d * 10 + D[j] - '0') % (mod-1); ans = ans*modpow(fib.query(C), d) % mod; cout<