using namespace std;

#include <cstdio>
#define ll long long
#define IN "inversmodular.in"
#define OUT "inversmodular.out"

ll N,A;

ll pow(int x,int p)
{
	ll a;
	return (!p?1:(p&1?x * pow(x,p-1):(a = pow(x,p>>1))*a) ) % N;
}

int main()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%lld%lld",&A,&N);

	ll rez = pow(A,N-2);
	if( rez * A % N == 1)
		printf("%lld\n",rez);
	else
	{
		rez *= A;
		rez %= N;
		if(rez * A % N == 1)
			printf("%d\n",rez);
		else
			printf("%d\n",rez * A % N);
	}	
	return 0;
}