#include <bits/stdc++.h>

using namespace std;

const string NUMEFISIER="inversmodular";
ifstream fin(NUMEFISIER+".in");
ofstream fout(NUMEFISIER+".out");

void euclidExtins(int a, int b, int& x, int& y, int& d)
{
    if(b==0)
    {
        x=1; y=0; d=a;
        return;
    }
    int x1,y1,q=a/b;
    euclidExtins(b, a%b, x1, y1, d);
    x=y1;
    y=x1-q*y1;
}

int inversModular(int a, int mod)
{
    int x,y,d;
    euclidExtins(a, mod, x, y, d);
    assert(d==1);
    if(x<0)
        x+=mod;
    return x%mod;
}

int main()
{
    int a,n;
    fin>>a>>n;
    fout<<inversModular(a, n);
    return 0;
}