a,n = map(int,input().split())
mod = 10**8 
def large_mod(a,n,mod):
    res = 1
    while (n > 0):
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
ans = large_mod(a,n,mod)
print(mod)
print(ans)