#include <iostream>
#include <fstream>

using namespace std;

#define LL long long

LL modular_exponentiation(LL base, LL exponent, int MOD)
{
    if (exponent == 0)
        return 1;
    LL result = modular_exponentiation(base, exponent / 2, MOD) % MOD;
    result = (result * result) % MOD;
    if (exponent % 2 == 1)
        result = (result * base) % MOD;
    return result;
}

LL Phi(LL nr)
{
    LL cur = nr;
    for(LL i = 2; i * i <= nr; ++i)
    {
        if (nr % i == 0)
        {
            while(nr % i == 0)
                nr /= i;
            cur = (cur / i) * (i - 1);
        }
    }
    if (nr != 1)
        cur = cur / nr * (nr - 1);
    return cur;
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");

    LL A, N;
    fin >> A >> N;

    int MOD = N;

    LL x = Phi(N);
    fout << modular_exponentiation(A, x - 1, MOD);

    fin.close();
    fout.close();

    return 0;
}