#include <iostream>
#include <fstream>

using namespace std;

ifstream fin;
ofstream fout;

long long mod, a;

long long log_exp (long long base, long long power){
    long long to_return;

    if (power == 1ll) return (base%mod);

    long long aux = power % 2;
    switch (aux){
        case 0ll:
            to_return = log_exp((base%mod) * (base%mod), power/2) % mod;
            break;

        case 1ll:
            to_return = (base%mod * ((log_exp((base%mod) * (base%mod), power/2)) %mod));
            break;
    }

    return to_return;
}

int getphi(int n)
{
    int result = n; // Initialize result as n

    // Consider all prime factors of n and subtract their
    // multiples from result
    if (n % 2 == 0){
        while (n % 2 == 0)
            n /= 2;
        result -= result / 2;
    }

    for (int p = 3; p * p <= n; p+=2) {

        // Check if p is a prime factor.
        if (n % p == 0) {

            // If yes, then update n and result
            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }

    // If n has a prime factor greater than sqrt(n)
    // (There can be at-most one such prime factor)
    if (n > 1)
        result -= result / n;
    return result;
}


int main(void){
    fin.open("inversmodular.in");
    fin>>a>>mod;
    fin.close();

    long long result, exponent = getphi(mod);

    result = log_exp(a, (exponent-1));

    fout.open("inversmodular.out");
    fout<<(result%mod)<<"\n";
    fout.close();

    return 0;
}