a,n = map(int,input().split())
m = 10000019
a %= m
n %= m
print(m)
print((a**n)%m)