#include <fstream>
using namespace std;

ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

long long a, mod, rest[1005], x[1005], pas, cat, rez;

int main()
{
    cin >> a >> mod;
    rest[1] = a;
    rest[2] = mod;
    x[1] = 1;
    x[2] = 0;
    pas = 3;
    while(true)
    {
        cat = rest[pas-2]/rest[pas-1];
        rest[pas] = rest[pas-2]%rest[pas-1];
        x[pas] = x[pas-2]-x[pas-1]*cat;
        if(rest[pas] == 0)
        break;
        pas++;
    }
    rez = x[pas-1];
    while(rez < 0)
    rez+=mod;
    cout << rez;
}