A, N = map(int, input().split()) M = 10000000 print(M) print((A**N)%M) print("\n")