long n,m,t=1,x,y,p=129402307;main(i){for(;i=getchar()-10;x++)n=(n*10+i-38)%p;for(;i=getchar()-10;y+=!!m)m=(m*10+i-38)%~-p;for(i=27;i--;)t=t*t%p*(m>>i&1?n:1)%p;n=!printf("%d",n?t:x-1?!y:0);}