#include<stdio.h>
FILE *f,*g;
long i,d,ok,n,nr,x,a;
int main()
{ f=fopen("inversmodular.in","r"); g=fopen("inversmodular.out","w");
  fscanf(f,"%ld%ld",&a,&n);
  for(i=2;i<n;i++)
   { d=2; ok=0;
     while(!ok&&d<=i) 
		if(n%d==0&&i%d==0) ok=1; 
	    else 
		 if(d==2) d++; 
		 else d+=2;
	 if(!ok) nr++;
   }
  x=a;
  for(i=1;i<nr;i++) { x=x*a; x=x%n; }
  fprintf(g,"%ld",x);
  fclose(g);
  return 0;
}