def power(a,k,n) return 0 if a==0||n==0 return 1 if k==0 cmod=a%n k=k%(n-1) cv=(k%2)>0 ? cmod : 1 k>>=1 while k>0 do cmod=(cmod*cmod)%n cv=(cv*cmod)%n if (k%2)>0 k>>=1 end return cv end n=gets.to_i m=gets.to_i md=129402307 puts power(n,m,md)