#include <iostream>
#include <fstream>

using namespace std;
const int NMAX = 2e9;

ifstream fin ( "inversmodular.in" );
ofstream fout ( "inversmodular.out" );

/// AX + MOD * Y = 1

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

int main()
{
   int a, MOD; fin >> a >> MOD;
   int invers_mod, aux;
   extended_eu_alg ( a, MOD, invers_mod, aux );
   fout << (long long)( invers_mod + MOD ) % MOD;
    return 0;
}