#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;
}

int ridicareLog(int a, int b)
{
    int sol = 1;

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

        a *= a;

        b /= 2;
    }

    return sol;
}

int totient(int mod)
{
    int val = 1ull;

    int div = 2ull;
    int exp = 0ull;

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

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

        exp = 0;
    }

    div++;

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

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

            exp = 0;
        }

        div++;

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

    return val;
}

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

    int x, mod;

    in >> x >> mod;

    int putere = totient(mod);
    putere--;

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

    return 0;
}