IO.popen('g++ -xc++ -O2 -oZ - -lgmpxx -lgmp','w'){|io|io.puts DATA.read} IO.popen('./Z','r+'){|io|io.write $<.read;io.close_write;puts io.read} File.unlink('Z') __END__ #include #include #include using namespace std; typedef valarrayV; int M=1000000007; V z(4); V &g(const V &_x,const V &_y){ for(int i=0,j;i<2;i++)for(j=0;j<2;j++)z[i*2+j]=(_x[slice(i*2,2,1)]*_y[slice(j,2,2)]).sum()%M; return z; } main(){ cin.tie(0);ios::sync_with_stdio(false); long long T,r=1,c,z; for(cin>>T;T--;){ mpz_class d; cin>>c>>d; if(d>M-1)d%=M-1; V x(4),e(4); x[0]=x[1]=x[2]=e[0]=e[3]=1; for(c--;c;x=g(x,x),c>>=1)if(c&1)e=g(e,x); for(z=1;d!=0;c=c*c%M,d>>=1)if((d&1)!=0)z=z*c%M; r=r*z%M; } cout<