#include #define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++) const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; using namespace std; typedef long long ll; const ll MOD = 1e9+7; const ll MM = MOD-1; template class Mat { public: Mat() : mat(R, vector(C)) {} Mat& operator=(const Mat& rhs) { for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) { mat[i][j] = rhs[i][j]; } return *this; } vector& operator[](int r) {return mat[r];} const vector operator[](int r) const {return mat[r];} Mat& operator+=(const Mat rhs) { for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) { mat[i][j] += rhs.mat[i][j]; if (mat[i][j] >= mod) mat[i][j] %= mod; } return (*this); } Mat& operator-=(const Mat rhs) { for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) { mat[i][j] -= rhs.mat[i][j]; mat[i][j] %= mod; if (mat[i][j] < 0) mat[i][j] += mod; } return (*this); } const Mat operator+(const Mat rhs) const { Mat ret = (*this); ret += rhs; return ret; } const Mat operator-(const Mat rhs) const { Mat ret = (*this); ret -= rhs; return ret; } const Mat operator*(const Mat rhs) const { Mat ret; for (int i = 0; i < R; i++) { for (int k = 0; k < C; k++) { for (int j = 0; j < R; j++) { ret[i][j] += (*this)[i][k] * rhs[k][j]; if (ret[i][j] >= mod) ret[i][j] %= mod; } } } return ret; } void print() const { for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { cout << mat[i][j] << "\t"; } cout << endl; } } private: vector > mat; }; template Mat matrixPow(Mat a, ll N) { Mat ret; for (int i = 0; i < R; i++) ret[i][i] = 1; for (int i = 0; N>0; i++) { if ((N>>i)&1) { ret = ret*a; N -= (1ll< Mat2x2; ll getMod(const string& s) { int n = s.size(); ll ans = 0; for (int i = 0; i < n; i++) { ans *= 10; ans += (s[i]-'0'); ans %= MM; } return ans; } // x^p ll powmod(ll x, ll p, ll m = MOD) { if (x == 0) return 0; if (p == 0) return 1; if (p == 1) return x; if (p % 2 == 0) { ll tmp = powmod(x, p/2, m); return (tmp*tmp)%m; } else { ll tmp = powmod(x, p-1, m); return (tmp*x)%m; } } int main() { int N; cin >> N; ll ans = 1; Mat2x2 a; a[0][1] = a[1][0] = a[1][1] = 1; while (N--) { ll C; string D; cin >> C >> D; ll d = getMod(D); cout << d << endl; Mat2x2 b = matrixPow(a, C-1); ll tmp = b[1][0] + b[1][1] * 2; tmp %= MOD; ans *= powmod(tmp, d); ans %= MOD; } cout << ans << endl; return 0; }