import std.algorithm, std.array, std.container, std.range, std.bitmanip; import std.numeric, std.math, std.bigint, std.random, core.bitop; import std.string, std.regex, std.conv, std.stdio, std.typecons; const long mod = 10 ^^ 9 + 7; alias long[2][2] mat; mat modMulMat(mat a, mat b) { return [ [ ((a[0][0] * b[0][0]) % mod + (a[0][1] * b[1][0]) % mod) % mod, ((a[0][0] * b[0][1]) % mod + (a[0][1] * b[1][1]) % mod) % mod, ], [ ((a[1][0] * b[0][0]) % mod + (a[1][1] * b[1][0]) % mod) % mod, ((a[1][0] * b[0][1]) % mod + (a[1][1] * b[1][1]) % mod) % mod ] ]; } mat[] fibMemo() { auto memo = new mat[](size_t.sizeof * 8); memo[0] = [[1, 1], [1, 0]]; foreach (i; 1..size_t.sizeof * 8) memo[i] = modMulMat(memo[i - 1], memo[i - 1]); return memo; } long modFib(long n, mat[] fibMemo) { size_t m = n; long[2][2] r = [[1, 0], [0, 1]]; foreach (i; 0..size_t.sizeof * 8) if (bt(&m, i)) r = modMulMat(fibMemo[i], r); return r[0][0]; } long modPow(long a, long n) { auto memo = new long[](size_t.sizeof * 8); memo[0] = a; auto r = 1; foreach (i; 1..size_t.sizeof * 8) { if ((1 << i) > n) break; memo[i] = (memo[i - 1] * memo[i - 1]) % mod; } size_t m = n; foreach (i; 0..size_t.sizeof * 8) { if ((1 << i) > m) break; if (bt(&m, i)) r = (r * memo[i]) % mod; } return r; } void main() { auto n = readln.chomp.to!size_t; auto fibMemo = fibMemo(); auto r = 1; foreach (_; 0..n) { auto rd = readln.split; auto c = rd[0].to!long, d = BigInt(rd[1]); auto e = (d % (mod - 1)).to!long; auto f = modPow(modFib(c + 1, fibMemo), e); r = (r * f) % mod; } writeln(r); }