#include <iostream>
#include <fstream>
using namespace std;
long long mod;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long inversmodular1(long long a, long long n)
{
    long long i;
    for(i=1;i<=n-1;i++)
        if(a*i%n==1) return i;
    return -1;
}
long long phi(long long n)
{
   long long d=2, nr=n;
   while(n!=1)
   {
      if (n%d==0)
      {
         nr=nr/d*(d-1);
         while (n%d==0)
            n/=d;
      }
      if(d==2) d++;
      else d+=2;
      if(d*d>n) d=n;
   }
   return nr;
}
long long putere(long long a, long long b)
{
    long long p=1;
    while(b!=0)
    {
        if(b%2!=0) p=p*(a%mod)%mod;
        a=(a%mod)*(a%mod)%mod;
        b=b/2;
    }
    return p%mod;
}
long long inversmodular(long long a, long long n)
{
    long long fi=phi(n);
    fi--;
    return putere(a, fi);

}
int main()
{
    long long a, n;
    f>>a>>n;
    mod=n;
    g<<inversmodular(a, n);
    f.close();
    g.close();
    return 0;
}