while 1: a,n=map(int,raw_input().split());x,y=1,0;m=n while n:a,n,x,y=n,a%n,y,x-a/n*y print x%m