eval"A,B,C,D,N,X,Y,Z,W=#{`tr 
-! ,`}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