#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
void euclid_extins(int a,int b,int &x,int &y);
int invers_modular(int a);
int M;
int main()
{
    int a,ia;
    fin>>a>>M;
    ia=invers_modular(a);
    if (ia<0) ia+=M;
    fout<<ia<<'\n';
    return 0;
}
void euclid_extins(int a ,int b, int &x,int &y)
{
    int x1,y1;
    if (!b)
    {
        x=1; y=0; return;
    }
    euclid_extins(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
}
int invers_modular(int a)
{
    int x,y;
    euclid_extins(M,a,x,y);
    return y;
}