a, n = list(map(int, input().split()))
m = 10 ** 7
s = a ** n % m
print(m)
print(s)