#include <bits/stdc++.h>

using namespace std;

const int MOD = 1999999973;

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

        x = x2;
        y = y2;
    }
}

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

    long long a, b, x, y, d;
    fin >> a >> b;

    euclid( a, b, x, y, d );

    fout << (x % b + b) % b << '\n';
    
    return 0;
}