#include<stdio.h>

long long N,M;

long long find(long long nr)
{
	long long cur = nr;
	if (nr%2==0)
	{
          cur>>=1;
          while (nr%2==0)
               nr/=2;
     }

	for(long long i = 3;i * i <= nr; i+=2)
	{
		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);

     long long put = find(M) - 1;
	long long nr = N;
	long long rez = 1;

    for(long long p = 1;p <= put ; p=p<<1)
    {
	 	if (p & put)
               rez = (rez * nr) % M;
	  	nr = (nr * nr) % M;
	}
	printf("%lld\n",rez);
	return 0;
}