#include <cstdio>
using namespace std;
bool ciur[44723];
long long pawa(long long a,long long p,long long n)
{
  long long rez=1;
  a=a%n;
  while(p!=0)
  {
    if(p%2==1)
    {
      rez=(rez*a)%n;
      p--;
    }
    else
    {
        a=(a*a)%n;
        p/=2;
    }
  }
  return rez;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long x,y,phi,cy;
    scanf("%lld%lld",&x,&y);
    phi=y;
    cy=y;
    for(int i=2;i*i<=44722;++i)
    {
       if(ciur[i]==0)
       {
          int ci=i*i;
          while(ci<=44722)
          {
             ciur[ci]=1;
             ci+=i;
          }
       }
    }
    for(int i=2;i*i<=y && y!=1;++i)
    {
        if(ciur[i]==0 && y%i==0)
        {
           while(y%i==0)
              y/=i;
           phi/=i;
           phi*=i-1;
        }
    }
    if(y!=1)
     {
        phi/=y;
        phi*=y-1;
     }
    printf("%lld",pawa(x,phi-1,cy));
    return 0;
}