m@main=readLn>>=putStrLn.show.head.([1,1,1,0]%)>>m
[a,b,c,d]#[e,f,g,h]=map(`rem`10^9)[a*e+b*g,a*f+b*h,c*e+d*g,c*f+d*h]
m%p|p<2=m|rem p 2<1=m#m%(div p 2)|1>0=m%(p-1)#m