def power(a,k,n)
    return 0 if a==0||n==0
    return 0 if k==0
    cmod=a%n
    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
puts power(n,m%(129402307-1),129402307)