#include<stdio.h>
FILE *f,*g;
long long a,n,x,p,i,m;
int main()
{ f=fopen("inversmodular.in","r"); g=fopen("inversmodular.out","w"); 
  fscanf(f,"%lld%lld",&a,&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=n-1; p--;
  m=a;
  for(i=2;i<=p;i++) m=(m*a)%n;  
  fprintf(g,"%lld",m);
  fclose(g);
  return 0;
}