#include <fstream>
#include <cmath>

using namespace std;

unsigned long long ridicareLog(unsigned long long a, unsigned long long b, unsigned long long mod)
{
    unsigned long long sol = 1ull;

    while (b > 0ull)
    {
        if (b % 2ull == 1ull)
        {
            sol *= a;

            sol %= mod;
        }

        a *= a;
        a %= mod;

        b /= 2ull;
    }

    return sol;
}

unsigned long long ridicareLog(unsigned long long a, unsigned long long b)
{
    unsigned long long sol = 1ull;

    while (b > 0ull)
    {
        if (b % 2ull == 1ull)
        {
            sol *= a;
        }

        a *= a;

        b /= 2ull;
    }

    return sol;
}

unsigned long long totient(unsigned long long x)
{
    unsigned long long val = 1ull;

    unsigned long long div = 2ull;
    unsigned long long exp = 0ull;

    while (x % div == 0ull)
    {
        exp++;
        x /= div;
    }

    if (exp > 0ull)
    {
        val *= ridicareLog(div, exp - 1) * (div - 1ull);

        exp = 0ull;
    }

    div++;

    while (x > 1ull)
    {
        while (x % div == 0)
        {
            exp++;
            x /= div;
        }

        if (exp > 0)
        {
            val *= ridicareLog(div, exp - 1) * (div - 1ull);

            exp = 0ull;
        }

        div++;

        if (div * div > x)
        {
            div = x;
        }
    }

    return val;
}

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

    unsigned long long x, mod;

    in >> x >> mod;

    unsigned long long putere = totient(mod);
    putere--;

    out << ridicareLog(x, putere, mod) << '\n';

    return 0;
}