#include <iostream>
#include <fstream>

using namespace std;


int extended_euclidean(int a, int b)
{
    int r[4], s[4], t[4], q;
    r[1]=a;
    r[2]=b;
    s[1]=1;
    s[2]=0;
    t[1]=0;
    t[2]=1;

    q=a/b;
    r[3]=a-q*b;
    s[3]=s[1]-q*s[2];
    t[3]=t[1]-q*t[2];

    while(r[3]!=0){
        q=r[2]/r[3];
        r[0]=r[2]-q*r[3];
        s[0]=s[2]-q*s[3];
        t[0]=t[2]-q*t[3];

        r[1]=r[2];
        r[2]=r[3];
        r[3]=r[0];

        s[1]=s[2];
        s[2]=s[3];
        s[3]=s[0];

        t[1]=t[2];
        t[2]=t[3];
        t[3]=t[0];
    }
    while(s[2] < 0){
        s[2] = s[2] + b;
    }
    return s[2];
}


int main()
{
    ifstream input("inversmodular.in");
    ofstream output("inversmodular.out");
    int A, N;
    input >> A >> N;
    output << extended_euclidean(A, N);
    return 0;
}