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 rez1 = pow(A,N-2);
	if( rez1 * A % N == 1)
		printf("%lld\n",rez1 % N);
	else
		printf("%lld\n",(rez1 * A) % N * A);
	return 0;
}