#include<stdio.h>
#define ll long long
FILE*f=fopen("inversmodular.in","r");
FILE*g=fopen("inversmodular.out","w");
ll a,n;
ll phi(ll n)
 {
 int rez=n;
 ll i;
 for(i=2;i*i<=n;++i)
  {
  if(n%i==0)
   {
   while(n%i==0) n/=i;
   rez=rez-rez/i;
   }
  }
 if(n>1)
  {
  rez=rez-rez/n;
  }
 return rez;
 }
int main()
 {
 fscanf(f,"%lld %lld",&a,&n);
 ll rez=1,b=phi(n)-1;
 while(b)
  {
  if(b%2==0) {a=(a*a)%n;b/=2;}
  else{ rez=(rez*a)%n; --b;}
  }
 fprintf(g,"%lld\n",rez);
 return 0;
 }