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

long long extended_gcd(long long a, long long b, long long *x, long long *y){
  if(b == 0){
    *x = 1;
    *y = 0;
    return a;
  }

  long long x1 = 0, y1 = 0;
  long long gcd = extended_gcd(b, a % b, &x1, &y1);

  *x = y1;
  *y = x1 - (a / b) * y1;
  return gcd;
}

long long mod_inverse(long long a, long long n){
  long long x = 0, y = 0;
  extended_gcd(a, n, &x, &y);

  x = x % n;
  if(x < 0)
    x += n;
  return x;
}

int main(void){
  FILE *fin = fopen("inversmodular.in", "r");
  if(fin == NULL){
    perror("inversmodular.in");
    return 1;
  }

  long long a = 0, n = 0;
  fscanf(fin, "%lld %lld", &a, &n);
  fclose(fin);

  FILE *fout = fopen("inversmodular.out", "w");
  if(fout == NULL){
    perror("inversmodular.out");
    return 1;
  }

  long long result = mod_inverse(a, n);
  fprintf(fout, "%lld\n", result);
  fclose(fout);

  return 0;
}