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