#include <fstream>
#include <iostream>

using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

long long a,n;
long long tmp;

long long get_tmp()
{
   int s = n, c = n;
   for(long long i = 2; i * i <= n; i++)
   {
       if(c % i == 0)
       {
           s = s - s / i;
           while(c % i == 0)
           {
               c = c / i;
           }
       }
   }
   if(c != 1)
        s = s - s/c;
   return s;
}

long long put()
{
    long long i = a;
    a = 1;

    for(;tmp > 0;)
    {
        if(tmp % 2 == 1)
        {
            a=(a * i) % n;
            tmp--;
        }
        i = (i * i) % n;
        tmp = tmp / 2;
    }
    return a;
}

int main()
{
    in >> a >> n;

    tmp = get_tmp() - 1;

    out << put();
}