main@m=getLine>>=print.f.map read.words>>m;f[a,b,c]|b<1=1|0<1=a^mod b 2*f[a,div b 2,c]^2`mod`c