#include using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back((a)) #define all(x) (x).begin(),(x).end() #define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x)) #define fi first #define se second #define dbg(x) cout<<#x" = "<<((x))< ostream& operator<<(ostream& o, const pair &p){o<<"("< ostream& operator<<(ostream& o, const vector &v){o<<"[";for(T t:v){o<> mat; // return A*B mat mat_mul(const mat &A, const mat &B){ int n=A.size(), m=B[0].size(), l=B.size(); mat ret(n, vector(m, 0)); rep(i,n) rep(k,l) if(A[i][k]!=0) rep(j,m){ (ret[i][j] += A[i][k] * B[k][j]) %= MOD; } return ret; } // A^p mat mat_pow(const mat &A, long p){ int n = A.size(); mat tmp(A), ret(n, vector(n,0)); rep(i,n) ret[i][i] = 1; while(p>0){ if(p&1) ret = mat_mul(tmp, ret); tmp = mat_mul(tmp, tmp); p /= 2; } return ret; } // x^n mod p long mod_pow(long x, long n, long p=MOD){ long res=1; x %= p; while(n>0){ if(n&1) res=res*x%p; x=x*x%p; n>>=1; } return res; } long mod_from_str(string n, long m=MOD-1){ long ret = 0; for(auto c : n){ ret = (ret*10 + c - '0')%m; } return ret; } int main(){ int n; cin>>n; long ans = 1; const mat fib = mat({{1,1},{1,0}}); rep(i,n){ long c; string d; cin>>c>>d; long dd = mod_from_str(d, MOD-1); mat p = mat_pow(fib, c+1); c = p[0][0] % MOD; ans *= mod_pow(c, dd); ans %= MOD; } cout << ans << endl; return 0; }