#define _CRT_SECURE_NO_WARNINGS //#define _GLIBCXX_DEBUG #include using namespace std; typedef long long ll; typedef vector vi; typedef vector vvi; typedef pair pii; #define all(c) (c).begin(), (c).end() #define loop(i,a,b) for(ll i=a; i istream & operator>>(istream & is, vector &); template ostream & operator<<(ostream & os, vector const &); template typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple const &){} template typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple const & t){ os << (n==0?"":" ") << get(t); _ot(os, t); } template ostream & operator<<(ostream & os, tuple const & t){ _ot<0>(os, t); return os; } template typename enable_if<(n>=sizeof...(T))>::type _it(istream &, tuple &){} template typename enable_if<(n< sizeof...(T))>::type _it(istream & is, tuple & t){ is >> get(t); _it(is, t); } template istream & operator>>(istream & is, tuple & t){ _it<0>(is, t); return is; } template istream & operator<<(istream & is, pair & p){ return is >> p.first >> p.second; } template ostream & operator<<(ostream & os, pair const & p){ return os << "(" << p.first << ", " << p.second << ") "; } template istream & operator>>(istream & is, vector & v){ rep(i,v.size()) is >> v[i]; return is; } template ostream & operator<<(ostream & os, vector const & v){ rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os; } #ifdef DEBUG #define dump(...) (cerr<<#__VA_ARGS__<<" = "< struct mint { int x; explicit mint() : x(0) {} explicit mint(int y){ if((x=y%M+M) >= M) x-= M; } mint & operator += (mintCR m){ if((x += m.x) >= M) x-=M; return *this; } mint & operator -= (mintCR m){ if((x += M-m.x) >= M) x-=M; return *this; } mint & operator *= (mintCR m){ x = 1LL*x*m.x%M; return *this; } mint & operator /= (mintCR m){ x=(1LL*x*m.exp(M-2).x)%M; return *this; } mint operator + (mintCR m) const { return mint(*this) += m; } mint operator - (mintCR m) const { return mint(*this) -= m; } mint operator * (mintCR m) const { return mint(*this) *= m; } mint operator / (mintCR m) const { return mint(*this) /= m; } bool operator < (mintCR m) const { return x < m.x; } mint inv() const { return exp(M-2); } mint exp(long long t) const { mint e = *this, res = mint(1); for(; t; e*=e, t>>=1) if(t&1) res *= e; return res; } }; template ostream &operator << (ostream & os, mint m){ return os << m.x; } #define matCR mat const & template struct mat { vector> dat; int height, width; explicit mat(int height_, int width_) : dat(height_, vector(width_)), height(height_), width(width_){} vector const & operator [] (int i) const { return dat[i]; }; vector & operator [] (int i){ return dat[i]; }; mat & operator += (matCR x){ rep(i,height) rep(j,width) dat[i][j]+=x[i][j]; return *this; } mat & operator -= (matCR x){ rep(i,height) rep(j,width) dat[i][j]-=x[i][j]; return *this; } mat & operator *= (matCR b){ mat res(height, b.width); rep(i,height) rep(k,b.height) rep(j,b.width) res[i][j] += dat[i][k]*b[k][j]; return *this = res; } mat operator + (matCR x) const { return mat(*this) += x; } mat operator - (matCR x) const { return mat(*this) -= x; } mat operator * (matCR x) const { return mat(*this) *= x; } bool operator < (matCR x) const { return dat < x.dat; } mat exp(ll t) const { mat e = *this, res = id(height); for(; t; e*=e, t>>=1) if(t&1) res *= e; return res; } mat trans() const { mat t(width, height); rep(i,width) rep(j,height) t[i][j] = dat[j][i]; return t; } static mat id (int n) { mat res(n,n); rep(i,n) res[i][i] = T(1); return res; } }; bool getIntMod(ll & x, ll M){ char c; while(1){ c = getchar(); if(c=='-' || c==EOF || isdigit(c)) break; } if(c==EOF) return false; int sign = c=='-' ? -1 : 1; x = c=='-' ? 0 : c-'0'; while(1){ c = getchar(); if(!isdigit(c)) break; x = x*10 + c-'0'; x %= M; } x*=sign; return true; } bool getIntMod(int & x, ll M){ ll y; bool res = getIntMod(y, M); x = y; return res; } int const mod = 1000000007; typedef mint modint; typedef mat matrix; modint fibonacci(ll n){ matrix a(2,2); a[0][0] = modint(0); a[0][1] = modint(1); a[1][0] = modint(1); a[1][1] = modint(1); matrix b(2,1); b[0][0] = modint(1); b[1][0] = modint(2); matrix ans = a.exp(n) * b; return ans[0][0]; } int main(){ int n; while(cin >> n){ modint ans(1); rep(i,n){ ll c,d; cin >> c; getIntMod(d,mod-1); auto x = fibonacci(c); dump(x); ans *= x.exp(d); } cout << ans << endl; } }