a, n = list(map(int, input().split()))
s = a ** n
M = 123456789
ans = s % M
print(M)
print(ans)