NTL_1_B: Power

べき乗
10^9乗なんてまともにやると大変なので
m^2n = m^n * m^nという関係を使ってlog nのオーダにしてやる

余りを求めろとなってるのは
a * b % q == (a % q) * (b % q)だから毎回余りをとってやればよかろう

1000000007で割るというのは32ビットで収まるように、
いや2乗しても64ビットに収まるように、ってことかな

def power(m, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        k = power(m, n // 2)
        return k * k % 1000000007
    else:
        k = power(m, (n - 1) // 2)
        return k * k * m % 1000000007

m, n = [int(x) for x in input().split()]
print(power(m, n))

いったんpower(m, n // 2)を変数に入れてやるのが大事
うっかりreturn power(m, n // 2) * power(m, n // 2)とか書いてしまうと
nのオーダになってしまう