#include<cstdio>
int main(){
  long long a,n,d,p,cn;
  long long phi,rez;
  freopen("inversmodular.in","r",stdin);
  freopen("inversmodular.out","w",stdout);
  scanf("%lld%lld",&a,&n);
  cn=n;
  phi=n;
  d=2;
  while(d*d<=n){
    if(n%d==0){
      phi=(phi/d)*(d-1);
      while(n%d==0)
        n/=d;
    }
    d++;
  }
  if(n!=1)
    phi=(phi/n)*(n-1);
  p=phi-1;
  rez=1;
  n=cn;
  a=a%n;
  while(p!=0){
    if(p%2==1){
      rez=(rez*a)%n;
      p--;
    }
    else{
      p/=2;
      a=(a*a)%n;
    }
  }
  printf("%lld",rez);
  return 0;
}