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