a,  n = map(int,input().split())
A=a
M=10**7
if(n>=3163):
    a=(a**3163)%M
    n-=3163
print(M)
print((a*(A**n))%M)