#include <bits/stdc++.h>

using namespace std;

long long a, P;

///phi(n)=n*((p1-1)/p1)*...*(pk-1)/pk)
/// unde p1,...pk sunt numerele prime din descompunerea
/// in factori ai lui n
int Phi(int n)
{
    int d, sol;
    d = 2;
    sol = n;
    while (n > 1 && d * d <= n)
    {
        if (n % d == 0)
        {
            while (n % d == 0)
                n /= d;
            sol /= d;
            sol *= (d - 1);
        }
        d++;
    }
    if (n > 1)
    {
        sol /= n;
        sol *= (n - 1);
    }
    return sol;
}

long long Putere(long long x, int n)
{
    long long rez;
    rez = 1;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            n--;
            rez = (rez * x) % P;
        }
        n /= 2;
        x = (x * x) % P;
    }
    return rez;
}

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

    fin >> a >> P;
    sol = Putere(a, Phi(P) - 1);
    fout << sol << "\n";

    fin.close();
    fout.close();
    return 0;
}