#include<bits/stdc++.h>

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


long long a,n,x,y;

void read()
{
	fin>>a>>n;
}

void invmod(long long u,long long v,long long &x,long long &y)
{
	if(!v)
     {
        x=1;
        y=0;
        return;
     }

	long long X,Y;
	invmod(v,u%v,X,Y);
	x=Y;
	y=X-(u/v)*Y;

}

void solve()
{
	invmod(a,n,x,y);

	while(x<0)
        x+=n;

	fout<<x;
}




int main()
{
	read();
	solve();

	return 0;
}