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
Note that non-ascii characters in the above source code will be escaped (such as \x9f).