#include <iostream>
#include <fstream>

using namespace std;

int m;

void euclid( int a, int b, long long& x, long long& y ) {
    if ( b == 0 ) {
        x = 1;
        y = 0;
    } else {
        long long x0, y0;
        euclid( b, a % b, x0, y0 );
        x = y0 % m;
        y = ( (long long)x0 - (long long)( a / b ) * y0 ) % m;
    }
}
int main() {
    ifstream fin( "inversmodular.in" );
    ofstream fout( "inversmodular.out" );
    int a;
    long long x, y;
    fin >> a >> m;
    euclid( a, m, x, y );
    fout << x;
    return 0;
}