m@main=getLine>>=print.f.map read.words>>m
f[a,b,c]=mod(a^mod b 2*f[a,div b 2,c]^min 2b)c