#include <fstream>

using namespace std;

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

int A, N;

int calcnr(long long nr)
{
    long long rez = nr;
    for(long long i = 2; i * i <= nr; i++)
    {
        if(nr % i == 0)
        {
            while(nr % i == 0)
                nr /= i;
            rez = (rez / i) * (i - 1);
        }
    }
    if(nr != 1)
        rez = rez / nr * (nr - 1);
    return (int)rez;
}

int putere(int n, int p)
{
    if(p == 0)
        return 1;
    if(p == 1)
        return n % N;

    if(p % 2)
        return ((long long)n * putere(((long long)n * n) % N, p / 2)) % N;
    return putere(((long long)n * n) % N, p / 2) % N;
}

int main()
{
    in >> A >> N;

    out << putere(A, calcnr(N) - 1) << '\n';
    return 0;
}