#include <bits/stdc++.h>

using namespace std;

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

int invMod( int a, int n ) {
  long long d, x, y;
  euclid( a, n, d, x, y );
  return (x % n + n) % n;
}

int main() {
  FILE *fin, *fout;
  int a, n;

  fin = fopen( "inversmodular.in", "r" );
  fscanf( fin, "%d%d", &a, &n );
  fclose( fin );

  fout = fopen( "inversmodular.out", "w" );
  fprintf( fout, "%d\n", invMod( a, n ) );
  fclose( fout );

  return 0;
}