#include using namespace std; #define int long long #define MOD 1000000007 typedef vector vec; typedef vector mat; mat mat_mul (mat A, mat B) { mat C(A.size(), vec(B[0].size())); for (int i=0; i0) { if (n&1) B = mat_mul(B, A); A = mat_mul(A, A); n >>= 1; } return B; } int mod_pow(int a, int n) { int res = 1; while (n>0) { if (n&1) res = res*a%MOD; a = a*a%MOD; n >>= 1; } return res; } signed main() { int N; cin >> N; int ans = 1; for (int i=0; i> Ci; string Di; cin >> Di; mat A(2, vec(2)); A[0][0] = 1; A[0][1] = 1; A[1][0] = 1; A[1][1] = 0; A = mat_pow(A, Ci+2); int Fi = A[1][0]; int a = 1; for (auto& Dii : Di) { a = mod_pow(a, 10); a = a*mod_pow(Fi, Dii-'0'); a %= MOD; } ans *= a; ans %= MOD; } cout << ans << endl; }