#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int aa,nn;
#define ll long long
ll MOD;

int phi(int n)
{
    int result=1;
    for(int i=2;i*i<=n;++i)
    {
      int produs=1;
      while (n%i==0)
      {
          n/=i;
          produs*=i;
          result*=(produs-(produs/i));
      }
    }
    if (n>1) result*=(n-1);
    return result;
}
inline ll lp(ll a,ll b)
{
    if (b==1) return a%MOD;
    if (b==0) return 1;
    if (b%2) return (a*lp(a,b-1))%MOD;
    return (lp(a,b/2)*lp(a,b/2))%MOD;
}
int invers (int a,int putere)
{
    MOD=putere;
    return lp(a,phi(putere)-1);
}
int main()
{
    f>>aa>>nn;
g<<invers(aa,nn)<<'\n';


  f.close();
  g.close();
    return 0;
}