#include <iostream>
#include <fstream>
using namespace std;
int mod;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int inversmodular1(int a, int n)
{
    int i;
    for(i=1;i<=n-1;i++)
        if(a*i%n==1) return i;
    return -1;
}
int phi(int n)
{
   int 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;
}
int putere(int a, int b)
{
    int 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;
}
int inversmodular(int a, int n)
{
    int fi=phi(n);
    fi--;
    return putere(a, fi);

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