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