#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin;
ofstream fout;

long long mod, a;
long long i, j;


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

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

    // Consider all prime factors of n and subtract their
    // multiples from result
    for (long long p = 2; p * p <= n; ++p) {

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

    return result;
}

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

    long long exponent, result;

    exponent = getphi(a);

    result = log_exp(a, exponent);

    result %= mod;

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

    return 0;
}