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