#include <iostream>
#include <fstream>

using namespace std;

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

long long int phi(long long int n)
{
    long long int result = n;
    for (long long int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

long long int expo(long long int baza, long long int exp, long long int Mod)
{
    long long solutie = 1LL, acc = 0LL;
    acc += baza;
    for (long long int i = 1; i <= exp; i *= 2)
    {
        if ((i & exp))
        {
            solutie *= acc;
            if (solutie >= Mod)
                solutie %= Mod;
        }
        acc *= acc;
        if (acc >= Mod)
            acc %= Mod;
    }
    return ((long long int)solutie);
}

long long invers_modular(long long n, long long fi, long long mod) {return expo(n, fi - 1, mod);}

int main()
{
    long long a, b, fct_eu, rezultat;
    fin >> a >> b;
    fct_eu = phi(b);

    rezultat = invers_modular(a, fct_eu, b);
    fout<<rezultat;
    return 0;
}