#include<stdio.h>

#define LL long long





LL N,M;



LL getphi(LL nr)

{

	LL cur = nr;

	for(LL i = 2;i * i <= nr; ++i)

	{

		if (nr % i == 0)

		{

			while(nr % i == 0)nr /= i;

			cur = (cur / i) * (i - 1);

		}

	}

        if (nr != 1) cur = cur / nr * (nr - 1);

	return cur;

}



int main()

{

	freopen("inversmodular.in","r",stdin);

	freopen("inversmodular.out","w",stdout);

	scanf("%lld %lld\n",&N,&M);

        LL put = getphi(M) - 1;

	LL nr = N;

	LL crt = 1;

    for(LL p = 1;p <= put;p <<= 1)

    {

	 	if (p & put) crt = (crt * nr) % M;

	  	nr = (nr * nr) % M;

	}

	printf("%lld\n",crt);

	return 0;

}