#include <stdio.h>

long long ins,inv;

void gsd(long long &x,long long &y,int a,int b)
{
 if (!b) {x=1;y=0;}  
 else
 {
     gsd(x,y,b,a%b);
     long long aux = x;
     x =y;
     y = aux-y*(a/b);
 }  
     
}
int main()
{
 FILE *in = fopen("inversmodular.in","r");
 FILE *out = fopen("inversmodular.out","w");
 
 int n,m;
 
 fscanf(in,"%d %d",&n,&m);
 
 gsd(inv,ins,n,m);
 
 while (inv<=0) inv = m+inv%m;
 
 fprintf(out,"%lld",inv);
}