#include<stdio.h>
FILE *f,*g;
long long a,n,x,p,i,m,val;
long long lgput(long long x,long long n)
{ if(n==0) return 1;
  else if(n%2) 
    { long long q=lgput(x,n/2);
      return (((q*q)%val)*x)%val;
	}
  else { long long q=lgput(x,n/2);
         return (q*q)%val; 
       }
}  
int main()
{ f=fopen("inversmodular.in","r"); g=fopen("inversmodular.out","w"); 
  fscanf(f,"%lld%lld",&a,&n); val=n;
  x=n; p=n;
  for(i=2;i*i<=x;i++)
    if(x%i==0) 
       { while(x%i==0) x/=i;
         p=(p/i)*(i-1);
	   }
  if(x!=1) p=(p/x)*(x-1); p--;
  fprintf(g,"%lld",lgput(a,p));
  fclose(g);
  return 0;
}