eval"A,B,C,D,N="+$<.read.split*?,
x,y,z,w=1,0,0,1
(N%8).times{x,y,z,w=x-z,y-w,x+z,y+w}
p ((x+=z)*(x>0?B: A)+(y+=w)*(y>0?D: C))*16.pow(N/8,M=10**9+7)%M