a, n = map(int, input().strip().split(' '))
M = 10000000

ans = pow(a, n, M)
print(M)
print(ans)