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)