#include<iostream>
#include<fstream>

using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

long long int k, a, P;

int Phi(int n)
{
    int w = n;
    int d=2;

    if (n % d == 0)
    {
        w /= d;
        w *= (d-1);
        while (n%d == 0)
        n = n/d;
    }
    d = 3;

    while (n!=1 && d*d <= n)
    {
      if (n%d == 0)
      { w /= d;
        w *= (d-1);
      while (n%d == 0)
       n = n/d;
      }
      d=d+2;
    }
    if (n!=1)
    { w /= n;
     w *= (n-1);
    }
    return w;
}

void Ridicare_Putere(long long int x, long long int k)
{
    int p = 1;
    while (k > 0)
    {
        if (k & 1 == 1)
        {
            k--;
            p = ((p%P) * (x%P)) % P;
        }
        else
        {
            k = k >> 1;
            x  = ((x%P) * (x%P)) % P;
        }
    }
    fout << p << "\n";
}

int main ()
{
   fin >> a >> P;
   k = Phi(P);
   Ridicare_Putere(a, k-1); /// calculare a ^ (k-1) % P
   fin.close();
   fout.close();
   return 0;
}