#include<stdio.h>
#include<math.h>

long long A,B;
int bin[50];
long long oldB;
long long phi;
long long fct;
long long p;


int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    scanf("%lld %lld",&A,&B);
    oldB = B;
    long long fct = 1;
    phi = B;
    while (B != 1)
      {
          fct++;
          p = 0;

          while (B % fct == 0)
            {
                B /= fct;
                p ++;
            }
           if (p) phi = (phi * (fct - 1)) / fct;
           if (fct > sqrt(B))
            {
            phi = (phi * (B - 1)) / B;
            B = 1;
            }
      }

    phi--;
    while (phi)
      {
          bin[++bin[0]] = phi % 2;
          phi /= 2;
      }
    long long p = 1;
    for(int i = 1; i <= bin[0]; i++)
     {
      p = (p * p) % oldB ;
        if (bin[i])
          p = (p * A) % oldB;
     }
    printf("%lld \n",p);
    return 0;
}