using System; using System.Collections; using System.Collections.Generic; using System.Numerics; using BI=System.Numerics.BigInteger; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ Mat[] Fib=new Mat[80]; Fib[0]=new Mat(1,0,0,1); Fib[1]=new Mat(1,1,1,0); for(int i=2;i<80;i++)Fib[i]=Fib[i-1]*Fib[i-1]; long Ans=1; for(int i=0;i2){ long t=C[i]-2; Mat E=new Mat(1,0,0,1); //Console.WriteLine(E.a+" "+E.b+" "+E.c+" "+E.d); for(int ii=1;ii<61;ii++){ if(((t>>(ii-1))&1)>0){ E=E*Fib[ii]; //Console.WriteLine(E.a+" "+E.b+" "+E.c+" "+E.d); } } val=(E.a*3+E.b*2)%mod; } //Console.WriteLine(val); long tot=1; long[] xx=new long[800]; xx[0]=1; xx[1]=val; for(int ii=2;ii<800;ii++){ xx[ii]=(xx[ii-1]*xx[ii-1])%mod; } for(int ii=1;ii<800;ii++){ if((D[i]>>(ii-1))%2==1){ tot*=xx[ii]; tot%=mod; } } Ans*=tot; Ans%=mod; } Console.WriteLine(Ans); } class Mat{ public long a,b,c,d; public Mat(long aa,long bb,long cc,long dd){ a=aa;b=bb;c=cc;d=dd; } public static Mat operator*(Mat x,Mat y){ return new Mat( ((x.a*y.a)%mod+(x.b*y.c)%mod)%mod, ((x.a*y.b)%mod+(x.b*y.d)%mod)%mod, ((x.c*y.a)%mod+(x.d*y.c)%mod)%mod, ((x.c*y.b)%mod+(x.d*y.d)%mod)%mod ); } } static long mod=(long)(1e9+7); int N; long[] C; BI[] D; public Sol(){ N=ri(); C=new long[N]; D=new BI[N]; for(int i=0;iint.Parse(e));} static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));} static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));} }