#include <cstdio>
using namespace std;
bool ciur[44722];
int pawa(int a,int p,int n)
{
  int rez=1;
  while(p!=0)
  {
    if(p%2==1)
    {
      rez=(rez*a)%n;
      p--;
    }
    else
    {
        a=(a*a)%n;
        p/=2;
    }
  }
  return rez;
}
int main()
{
    freopen("invmod.in","r",stdin);
    freopen("invmod.out","w",stdout);
    int x,y,phi,cy;
    scanf("%d%d",&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;
    printf("%d",pawa(x,phi-1,cy));
    return 0;
}