#include <iostream>
#include<fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long phi(long long nr)
{ long long fi=nr;
  for(long long i=2;i*i<=nr;i++)
  { if(nr%i==0)
   { while(nr%i==0)
       fi=fi/i*(i-1);
   }

  }
  if(nr!=1) fi=fi/nr*(nr-1);
    return fi;
}
int main()
 { long long n,r,a,b;

 r=1;
 f>>a>>n;
 b=phi(n)-1;
 while(b)
 { if(b%2) r=(r*a)%n;
 a=(a*a)%n;
 b/=2;

 }
 g<<r;
     return 0;
}