i;main(a,m,x){for(;~scanf("%d%d",&a,&m);printf("%d\n",x))for(x=1,i=m-2;i;i/=2)x=i&1?x*1ll*a%m:x,a=a*1ll*a%m;}