while 1:b,a=map(int,raw_input().split());q=a**9-1;print b**9/q%q