#include <stdio.h>
#include <stdlib.h>

void Euclid(long long a,long long b,long long *x,long long *y){
  if(b==0){
    *x=1;
    *y=0;
  }else{
    long long x0,y0;
    Euclid(b,a%b,&x0,&y0);
    *x=y0;
    *y=x0-(a/b)*y0;
  }
}

int main(){
  long long a,b,x,y;
  FILE *fin,*fout;
  fin=fopen("inversmodular.in","r");
  fout=fopen("inversmodular.out","w");
  fscanf(fin,"%lld%lld",&a,&b);

  Euclid(a,b,&x,&y);

  while(x<0){
    x+=b;
  }
  fprintf(fout,"%lld",x%b);

  fclose(fin);
  fclose(fout);
  return 0;
}