#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define int long long

void cmmdc(int a,int b,int &x,int &y){
  if(b==0){
    x=1;
    y=0;
  }else{
    cmmdc(b,a%b,x,y);
    int aux=x;
    x=y;
    y=aux-y*(a/b);
  }
}

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

  cmmdc(a,b,x,y);

  while(x<0){
    x%=b;
    x+=b;
  }

  fprintf(fout,"%lld",x);

  fclose(fin);
  fclose(fout);
}