#include <fstream>
#include <iostream>


using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");


struct vec
{
    int a1, a2;
};

int A, N, sol;

int main()
{
    int aux, a, n;
    vec v1, v2, v3;
    fin>>A>>N;
    a=A, n=N;
    v1.a1=v2.a2=1;
    v1.a2=v2.a1=0;
    if(A==1)
    {
        fout<<1;
        return 0;
    }
    while(n%a)
    {
        v3.a1=v1.a1-(n/a)*v2.a1;
        v3.a2=v1.a2-(n/a)*v2.a2;
        aux=n%a;
        n=a;
        a=aux;
        v1=v2;
        v2=v3;
    }
    sol=v2.a2%N;
    if( sol>=0 )
        fout<<sol;
    else
        fout<<N+sol;
    return 0;
}