#include<stdio.h>
long long N,M;



long long getphi(long long nr)

{

 long long cur = nr;

 for(long long 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);

        long long put = getphi(M) - 1;

 long long nr = N;

 long long crt = 1;

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

    {

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

    nr = (nr * nr) % M;

 }

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

 return 0;

}