// includes #include using namespace std; // macros #define pb emplace_back #define mk make_pair #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define rep(i, n) FOR(i, 0, n) #define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--) #define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr) #define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr) #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) #define bit(n) (1LL<<(n)) // functions template bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;} template bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;} template istream &operator>>(istream &is, vector &vec){for(auto &v: vec)is >> v; return is;} template ostream &operator<<(ostream &os, const vector& vec){for(int i = 0; i < vec.size(); i++){ os << vec[i]; if(i + 1 != vec.size())os << " ";} return os;} template ostream &operator<<(ostream &os, const set& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template ostream &operator<<(ostream &os, const unordered_set& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template ostream &operator<<(ostream &os, const multiset& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template ostream &operator<<(ostream &os, const unordered_multiset& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template ostream &operator<<(ostream &os, const pair &p){os << p.first << " " << p.second; return os;} template ostream &operator<<(ostream &os, const map &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;} template ostream &operator<<(ostream &os, const unordered_map &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;} // types using ll = long long int; using P = pair; // constants const int inf = 1e9; const ll linf = 1LL << 50; const double EPS = 1e-10; const int mod = 1000000007; const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, -1, 0, 1}; // io struct fast_io{ fast_io(){ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20);} } fast_io_; const ll B = 10000; const int BW = 4; struct BigInt{ vector digit; BigInt(ll a = 0){ digit.emplace_back(a); normalize(); } BigInt(const string &s){ from_string(s); } void from_string(const string &s){ digit.clear(); int i; for(i = (int)s.size() - BW; i >= 0; i-=BW){ digit.emplace_back(stol(s.substr(i, BW))); } i += BW; if(i > 0)digit.emplace_back(stol(s.substr(0, i))); } void normalize(){ ll c = 0; for(int i = 0; i < digit.size(); i++){ while(digit[i] < 0){ if(i + 1 == digit.size())digit.emplace_back(0); digit[i+1]--; digit[i] += B; } ll a = digit[i] + c; digit[i] = a % B; c = a / B; } while(c){ digit.emplace_back(c % B); c /= B; } for(int i = (int)digit.size() - 1; i >= 1; i--){ if(digit[i] == 0){ digit.pop_back(); }else{ break; } } } size_t size(){ return digit.size(); } BigInt& operator=(ll a){ digit.resize(1, a); normalize(); return *this; } BigInt& operator=(const string &s){ from_string(s); return *this; } } ZERO(0), ONE(1); ostream &operator<<(ostream &os, const BigInt &b){ os << b.digit[b.digit.size() - 1]; for(int i = (int)b.digit.size() - 2; i >= 0; i--){ os << setw(BW) << setfill('0') << b.digit[i]; } return os; } istream & operator>>(istream &is, BigInt &b){ string s; is >> s; b.from_string(s); return is; } bool operator<(const BigInt &x, const BigInt &y){ if(x.digit.size() != y.digit.size())return x.digit.size() < y.digit.size(); for(int i = x.digit.size() - 1; i >= 0; i--){ if(x.digit[i] != y.digit[i])return x.digit[i] < y.digit[i]; } return false; } bool operator>(const BigInt &x, const BigInt y){ return y < x; } bool operator<=(const BigInt &x, const BigInt &y){ return !(y < x); } bool operator>=(const BigInt &x, const BigInt &y){ return !(x < y); } bool operator!=(const BigInt &x, const BigInt &y){ return x < y || y < x; } bool operator==(const BigInt &x, const BigInt &y){ return !(x < y) && !(y < x); } BigInt operator+(const BigInt &x, ll a){ BigInt res = x; res.digit[0] += a; res.normalize(); return res; } BigInt operator+(const BigInt &x, const BigInt &y){ BigInt res = x; while(res.digit.size() < y.digit.size())res.digit.emplace_back(0); for(int i = 0; i < y.digit.size(); i++)res.digit[i] += y.digit[i]; res.normalize(); return res; } BigInt operator-(const BigInt &x, const BigInt &y){ BigInt res = x; assert(res.digit.size() >= y.digit.size()); for(int i = 0; i < y.digit.size(); i++)res.digit[i] -= y.digit[i]; res.normalize(); return res; } BigInt operator*(const BigInt &x, const BigInt &y){ BigInt z; z.digit.assign(x.digit.size() + y.digit.size(), 0); for(int i = 0; i < x.digit.size(); i++){ for(int j = 0; j < y.digit.size(); j++){ z.digit[i+j] += x.digit[i] * y.digit[j]; } } z.normalize(); return z; } BigInt operator*(const BigInt &x, ll a){ BigInt res = x; for(int i = 0; i < res.digit.size(); i++)res.digit[i] *= a; res.normalize(); return res; } pair divmod(const BigInt &x, ll a){ ll c = 0; BigInt res = x; for(int i = (int)res.digit.size() - 1; i >= 0; i--){ ll t = B * c + res.digit[i]; res.digit[i] = t / a; c = t % a; } res.normalize(); return make_pair(res, c); } BigInt operator/(const BigInt &x, ll a){ return divmod(x, a).first; } BigInt operator%(const BigInt &x, ll a){ return divmod(x, a).second; } pair divmod(const BigInt &x, const BigInt &y){ BigInt rx = x, ry = y; if(x.digit.size() < y.digit.size())return make_pair(ZERO, x); int F = B / (y.digit[y.digit.size() - 1] + 1); rx = rx * F; ry = ry * F; BigInt z; z.digit.assign(rx.digit.size() - ry.digit.size() + 1, 0); for(int k = (int)z.digit.size() - 1, i = (int)rx.digit.size() - 1; k >= 0; k--, i--){ z.digit[k] = (i + 1 < rx.digit.size() ? rx.digit[i+1]: 0) * B + rx.digit[i]; z.digit[k] /= ry.digit[ry.digit.size() - 1]; BigInt t; t.digit.assign(k + ry.digit.size(), 0); for(int m = 0; m < ry.digit.size(); m++){ t.digit[k+m] = z.digit[k] * ry.digit[m]; } t.normalize(); while(rx < t){ z.digit[k] -= 1; for(int m = 0; m < ry.digit.size(); m++){ t.digit[k+m] -= ry.digit[m]; } t.normalize(); } rx = rx - t; } z.normalize(); return make_pair(z, rx / F); } BigInt operator/(const BigInt &x, const BigInt &y){ return divmod(x, y).first; } BigInt operator%(const BigInt &x, const BigInt &y){ return divmod(x, y).second; } BigInt& operator+=(BigInt &x, ll a){ x = x + a; return x; } BigInt &operator+=(BigInt &x, const BigInt &y){ x = x + y; return x; } BigInt &operator-=(BigInt &x, const BigInt &y){ x = x - y; return x; } BigInt& operator*=(BigInt &x, const BigInt &y){ x = x * y; return x; } BigInt& operator/=(BigInt &x, const BigInt &y){ x = x / y; return x; } BigInt& operator%=(BigInt &x, const BigInt &y){ x = x % y; return x; } BigInt& operator/=(BigInt &x, ll a){ x = x / a; return x; } BigInt& operator%=(BigInt &x, ll a){ x = x % a; return x; } BigInt sqrt(const BigInt &x){ BigInt l = 1; BigInt r = x; while(r - l > BigInt(1)){ BigInt m = (r + l) / 2; if(m * m > x)r = m; else l = m; } return l; } template T extgcd(T a, T b, T &x, T &y){ T d = a; if(b != 0){ d = extgcd(b, a % b, y, x); y -= (a / b) * x; }else{ x = 1, y = 0; } return d; } template T modinv(T a, T m){ long long x = 0, y = 0; extgcd(a, m, x, y); x %= m; if(x < 0)x += m; return x; } template struct LMatrix{ vector> v; int n, m; LMatrix(int n_, int m_ = -1): n(n_), m(m_){ if(m < 0)m = n; v.resize(n); for(int i = 0; i < n; i++)v[i].resize(m); } void identity(){ assert(n == m); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ v[i][j] = (i == j ? 1: 0); } } } vector &operator[](size_t i){ return v[i]; } const vector &operator[](size_t i) const{ return v[i]; } LMatrix operator*(const LMatrix &r) const{ assert(m == r.n); int l = r.m; LMatrix res(n, l); for(int i = 0; i < n; i++){ for(int j = 0; j < l; j++){ res.v[i][j] = 0; for(int k = 0; k < m; k++){ res.v[i][j] = (res.v[i][j] + v[i][k] * r.v[k][j] % MOD) % MOD; } } } return res; } LMatrix operator+(const LMatrix &r) const{ assert(n == r.n); assert(m == r.m); LMatrix res(n, m); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ res[i][j] = (v[i][j] + r[i][j]) % MOD; } } return res; } LMatrix operator-(const LMatrix &r) const{ assert(n == r.n); assert(m == r.m); LMatrix res(n, m); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ res[i][j] = (v[i][j] - r[i][j]) % MOD; if(res[i][j] < 0)res[i][j] += MOD; } } return res; } template LMatrix operator*(T a) const{ LMatrix res = *this; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ res[i][j] = a * res[i][j] % MOD; } } return res; } LMatrix inv2() const{ assert(n == 2 && m == 2); long long det = v[0][0] * v[1][1] % MOD - v[0][1] * v[1][0] % MOD; if(det < 0)det += MOD; assert(det != 0); LMatrix res(2, 2); long long inv = modinv(det, (long long)MOD); res[0][0] = v[1][1]; res[1][1] = v[0][0]; res[1][0] = - v[1][0]; res[0][1] = - v[0][1]; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ res[i][j] %= MOD; res[i][j] = res[i][j] * inv % MOD; if(res[i][j] < 0)res[i][j] += MOD; } } return res; } }; template LMatrix operator*(T a, const LMatrix b){ return b * a; } template LMatrix powerm(LMatrix &a, long long n){ long long tmp = n; LMatrix curr = a; LMatrix res(a.n); res.identity(); while(tmp){ if(tmp % 2 == 1){ res = res * curr; } curr = curr * curr; tmp /= 2; } return res; } template T power(T a, T n, T mod) { T res = 1; T tmp = n; T curr = a; while(tmp){ if(tmp % 2 == 1){ res = (T)(res * curr % mod); } curr = (T)(curr * curr % mod); tmp >>= 1; } return res; } // dp[i][0] = dp[i-1][0] + dp[i-1][1] // dp[i][1] = dp[i-1][0] // | 1 1 | // | 1 0 | int main(int argc, char const* argv[]) { int n; cin >> n; ll res = 1; LMatrix<> lm(2, 2); lm[0][0] = 1; lm[1][0] = 1; lm[0][1] = 1; BigInt MOD = BigInt(mod); rep(i, n){ ll c; string d; cin >> c >> d; BigInt D(d); D %= (MOD - 1); ll dd = 0; ll ba = 1; for(int j = 0; j < min(3, (int)D.digit.size()); j++){ dd = (dd + ba * D.digit[j] % mod) % mod; ba = ba * (ll)B % mod; } auto p = powerm(lm, c); ll tmp = (p[0][0] + p[1][0]) % mod; if(tmp > 0)tmp = power(tmp, dd, mod); res = res * tmp % mod; } cout << res << endl; return 0; }