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