#include <fstream>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
long long N, M, S = 1, exp;

long long Get_Exp(int nr)
{
    long long sol = nr;
    for (int i = 2; i * i <= nr; i++)
    {
        int putdiv = 0;
        if (nr % i == 0)
        {
            while (nr % i == 0)
            {
                nr /= i;
                putdiv += 1;
            }
            sol = sol / i * (i - 1);
        }
    }

    if (nr != 1)
    {
        sol = sol / nr * (nr - 1);
    }
    return sol;
}

int main()
{
    fin >> N >> M;
    exp = Get_Exp(M) - 1;
    while (exp)
    {
        if (exp & 1) S = S * N % M;
        N = N * N % M;
        exp = (exp >> 1);
    }
    fout << S << '\n';
    fout.close();
    return 0;
}