inpl = lambda oneindex=False: list(map(lambda x: int(x)-int(bool(oneindex)),input().split()))
a, n = inpl()
M = 10**7 + 1
print(M)
print(pow(a,n,M))