procedure qsort(l,r:longint);

var i,j,t,m:longint;

begin i:=l; j:=r;

 m:=a[(i+j) div ];

 repeat

while a[i]<m do inc(i);

while m<a[j] do dec(j);

if i<=j then

  begin   t:=a[i]; a[i]:=a[j]; a[j]:=t;

inc(i); dec(j);  end;  until i>j;

 if i<r then qsort(i,r); if j>l then qsort(l,j);  end;  

procedure insert(x:longint);

var t,s,v:longint;

begin

  len:=len+; f[len]:=x; s:=len;

  while (s<>)and(f[s div ]>f[s]) do

   begin

     v:=f[s div ]; f[s div ]:=f[s]; f[s]:=v;

     s:=s div ;

   end;

end;

function get:longint;

var t,s,v:longint;

begin

  get:=f[]; f[]:=f[len]; len:=len-; t:=;

  while (t*<=len)or(t*+<=len) do

   begin

     if (t*+>len)or(f[t*]<f[t*+])

     then s:=t* else  s:=t*+;

     if f[t]>f[s] then

      begin

        v:=f[t]; f[t]:=f[s]; f[s]:=v; t:=s;

      end

  else break;

   end;

end;    

function phi(x:longint):longint;

var ans,i:longint;

begin

  ans:=x;

  for i:= to trunc(sqrt(x)) do

   begin

   if x mod i= then ans:=ans div i*(i-);

   while x mod i= do x:=x div i;

   end;

  if x<> then ans:=ans div x*(x-);

  exit(ans);

end;        

procedure work;

var i,j:longint;

begin

  p:=;

  for i:= to n do e[i]:=i;

  for i:= to n do

    if e[i]=i then

     begin j:=i;

     while j<=n do begin e[j]:=e[j] div i*(i-); inc(j,i); end;

     end;

  for i:= to n do

   begin

     if e[i]=i- then begin inc(p); prime[p]:=i; end;

   end;

end;

procedure work(n:longint);

var i,j:longint;

begin

  num:=;

  for i:= to n do g[i]:=true;

  for i:= to n do

   if g[i]=true then

    begin

      inc(num); prime[num]:=i;

      j:=i*;

      while j<=n do begin g[j]:=false; j:=j+i; end;

    end;

end;  

procedure fenjie(x:longint);

var i,y:longint;

begin

  t:=;y:=x;

  for i:= to num do

   begin

     if prime[i]>y div  then exit;

     if x mod prime[i]= then

     begin

     inc(t); w[t]:=prime[i];

     while x mod prime[i]= do x:=x div prime[i];

     end;

     if x= then break;

   end;

end;   

function quick(x,n,p:qword):qword;

var ans:qword;

begin

  ans:=;

  while n> do

  begin

   if n and > then ans:=cheng(ans,x,p);

   x:=cheng(x,x,p);

   n:=n>>;

  end;

  exit(ans);

end;

function cheng(x,n,p:qword):qword;

var ans:qword;

begin

 ans:=;

  while n> do

   begin

     if n and > then ans:=(ans+x) mod p;

     x:=(x+x) mod p;

     n:=n>>;

   end;

  exit(ans);

end;

for i:= to n do if u[i]= then begin inc(t); f[t]:=i; end;

  repeat

    x:=f[t]; dec(t); inc(num);

    new(p); p:=a[x];

    while p<>nil do

     begin

       y:=p^.data;

       dec(u[y]);

       if u[y]= then

        begin

          inc(t); f[t]:=y;

        end;

       p:=p^.next;

     end;

  until num=n;

procedure tarjan(x:longint);

var y:longint; p:point;

begin

  inc(s); low[x]:=s; dfn[x]:=s; inc(t); q[t]:=x;

  instack[x]:=true;

  new(p); p:=a[x];

  while p<>nil do

   begin

     y:=p^.x;

     if dfn[y]= then begin tarjan(y); low[x]:=min(low[x],low[y]); end

      else if instack[y]=true then low[x]:=min(low[x],dfn[y]);

     p:=p^.next;

   end;

  if dfn[x]=low[x] then

   begin

     inc(num);

     repeat

       y:=q[t]; dec(t); f[y]:=x;instack[y]:=false;

     until x=y;

   end;

end;

 for i:= to n do begin dfn[i]:=; low[i]:=; w[i]:=; instack[i]:=false; end;

  s:=; t:=; num:=;

  for i:= to n do if dfn[i]= then tarjan(i);     

procedure dfs(x,e:longint);

var p:point; y:longint;

begin

  s1[x]:=x; s2[x]:=x; new(p); p:=a[x];

  while p<>nil do

   begin

     y:=p^.x;

     if y=e then begin p:=p^.next; continue; end;

     dfs(y,x);

     if f1[y]+p^.v>f1[x] then

     begin

       f2[x]:=f1[x]; s2[x]:=s1[x];

       f1[x]:=f1[y]+p^.v; s1[x]:=y;

      end

     else

     if f1[y]+p^.v>f2[x] then

     begin

       f2[x]:=f1[y]+p^.v; s2[x]:=y;

     end;

     p:=p^.next;

   end;

  if f1[x]+f2[x]>f1[max]+f2[max] then

   max:=x;

end;       

  p[]:=; j:=;

  for i:= to m do

   begin

     while (j>)and(b[j+]<>b[i]) do j:=p[j];

     if b[j+]=b[i] then inc(j);

     p[i]:=j;

   end;

  j:=; kmp:=;

  for i:= to n do

    begin

      while (j>)and(b[j+]<>a[i]) do j:=p[j];

      if b[j+]=a[i] then inc(j);

      if j=m then begin inc(kmp); j:=p[j]; end;

    end;

procedure work;

var i,j:longint;

begin

  for i:= to  do

   for j:= to n do

    f[i+,j]:=f[i,f[i,j]];

end;

function lca(x,y:longint):longint;

var i,t:longint;

begin

  if deep[x]<deep[y] then begin t:=x; x:=y; y:=t; end;

  for i:= downto  do

   if ((deep[x]-deep[y])>>i)and = then x:=f[i,x];

  if x=y then exit(x);

  for i:= downto  do

   if f[i,x]<>f[i,y] then

   begin x:=f[i,x]; y:=f[i,y]; end;

  exit(f[,x]);

end;    

function dfs(x,color:longint):boolean;

var p:point; y:longint;

begin

  new(p); p:=w[x]; g[x]:=color;

  while p<>nil do

   begin

     y:=p^.x;

     if g[y]=color then exit(false);

     if (g[y]=)and(not dfs(y,-color)) then exit(false);

     p:=p^.next;

   end;

  exit(true);

end;

function cheak(s:longint):boolean;

var i:longint;

begin

  for i:= to n do g[i]:=;

  for i:= to n do

   if g[i]= then

    if not dfs(i,) then exit(false);

  exit(true);

end;

procedure make;

var i:longint;

begin

  f[]:=; g[]:=;

  for i:= to n do

   begin

     f[i]:=(f[i-]*i) mod num;

     g[i]:=g[i-]*quick(i,num-) mod num;

   end;

end;

function get(x,y:int64):int64;

var i:longint; t:int64;

begin

  if (x=)or(y=)or(x=y) then exit();

  exit(((f[x]*g[x-y]) mod num)*g[y] mod num);

end;

program asdf;

var

  a,m,x,y,t:longint;

function extgcd(a,b:longint;var x,y:longint):longint;

var d:longint;

begin

  if b<> then begin d:=extgcd(b,a mod b,y,x); y:=y-(a div b)*x; end

   else begin x:=;y:=; d:=a; end;

  exit(d);

end;

begin

  readln(a,m);

  x:=; y:=;

  t:=extgcd(a,m,x,y);

  writeln((x+m) mod m);

end.