#include<bits/stdc++.h>
using namespace std;
int invers_mod(int A,int N)
{
    int r,c,y;
    int y0=0,y1=1;
    int aux=N;
    while(A!=0)
    {
        r=N%A;
        c=N/A;
        N=A;
        A=r;
        y=y0-c*y1;
        y0=y1;
        y1=y;
    }
    while(y0<0)
    {
        y0=y0+aux;
    }
    return y0;
}
int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    int A,N;
    f>>A>>N;
    g<<invers_mod(A,N);
}