m = 10000000
a, n = [int(x) for x in input().split()]
print(m, a ** n % m, sep='\n')