#include <fstream>
using namespace std;

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

long long putere(long long bz, long long exp, int mod)
{
    long long rez = 1;
    while (exp != 0)
    {
        if (exp % 2 == 0)
        {
            bz *= bz;
            bz %= mod;
            exp /= 2;
        }
        else
        {
            rez *= bz;
            rez %= mod;
            --exp;
        }
    }
    return rez;
}

long long Phi(int nr)
{
    int cnr = nr;
    int divz = 2;
    int rez = nr;
    while (cnr != 1)
    { bool hai = false;
        while (cnr % divz == 0)
        {
            hai = true;
            cnr = cnr / divz;
        }
        if (hai == true)
        {rez -= rez / divz;
        }

        if (divz == 2) divz = 3;
        else divz = divz + 2;
    }
    return rez;
}

bool firicel(int nr)
{
    if (nr % 2 == 0) return false;
    for (int d = 3;d * d <= nr;++d)
        if (nr % d == 0)  return false;
    return true;
}

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

    if (firicel(n))
    {
        out<<putere(a,n - 2,n);
    }
    else{
    long long put = Phi(n) - 1;
    out << putere(a,put,n);}
}