g;t;u;a;n;f(m,p,i){i=p=m;for(t=2;i%t?t=i/(i/-~t),p-=i%t?0:p/t:(i/=t)-1;);p+=n?n--,f(p),t:a;for(n+=t=1;i*=2;)t=t*(p*i>>31?a:1LL)%m*t%m;}main(m){for(;u-t||~scanf(g="%d %d\n",&a,&m,n=!printf(g,n,u));f(m))u=t;}
Note that non-ascii characters in the above source code will be escaped (such as \x9f).