Given integers a, b and p. Calculate the value a^b mod p.
a^b
Two integers a and b (0 ≤ a, b ≤ 10^1000), each in a separate line.
10^1000
Print a^b mod p, where modulo p = 1000000007.