#include <bits/stdc++.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

pair<long long, long long> invers( long long b, long long a )
{
    if( a < b )
        swap(a,b);
    if( a%b == 1 )
    {
        pair<long long, long long> p;
        //cout << a << " " << b << " facem\n\n";
        p.first = 1;
        p.second = -(a/b);
        return p;
    }
    else
    {
        pair<long long, long long> p, f;
        p = invers( b, a%b );
        f.first = p.second;
        f.second = p.first - (a/b)*p.second;
        /*
        cout << a << " " << b << " " << a/b << "\n";
        cout << p.first << " " << p.second << "\n";
        cout << f.first << " " << f.second << "\n";
        cout << f.first*a + f.second*b << "\n";
        cout << f.first << " x " << a << " + " << f.second << " x " << b << "\n\n";
        */
        return f;
    }
}

int main() {
	long long a, M;
    f >> a >> M;
    //cout << euclid( 252, 105 );
    g << invers(a, M).second;
    return 0;
}