integer(16)::n,t(6,6)=0,a(6,6)=0,m=1000000007,r=166666668 do i=1,6 t(i,i+1)=1 t(i,1)=r a(i,i)=1 enddo read*,n do while(n>0) if(mod(n,2)==1)a=mod(matmul(a,t),m) t=mod(matmul(t,t),m) n=n/2 enddo print*,a(1,1) end