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

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

int main(){
  int n,p,x,y;
  long long a,s;
  FILE *fin, *fout;
  fin = fopen ("inversmodular.in", "r");
  fscanf (fin, "%lld%d", &a, &n);
  fclose(fin);

  euclid(a,n,&x,&y);
//  s=1;
//  p=n-2;
//  while(p>0){
//    if(p%2==1){
//      s*=a;
//      s%=n;
//    }
//    a*=a;
//    a%=n;
//    p/=2;
//  }

  fout=fopen("inversmodular.out","w");
  fprintf(fout,"%d\n",x);
  fclose(fout);
  return 0;
}