#include <fstream>
using namespace std;
ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");
long long a,b;
long long getphi(long long x)
{
      long long act=x;
      for(long long i=2;i*i<=x;++i)
      {
            if(x%i==0)
            {
                  while(x%i==0) x/=i;
                  act=act/i*(i-1);
            }
      }
      if(x!=1) act=act/x*(x-1);
      return act;
}
long long lgput(long long a,long long b,long long mod)
{
      long long x=1ll;
      while(b)
      {
        if(b%2) x=(x*a)%mod;
        a=(a*a)%mod;
        b=b/2;
      }
      return x;
}
int main()
{
      f>>a>>b;
      long long p=getphi(b)-1;
      g<<lgput(a,p,b);
      return 0;
}