#include <fstream>
#include <cmath>
using namespace std;

int phi(int n);
int modularPow(long long base, long long exponent, long long mod);

int main()
{
    int A, N;
    ifstream f("inversmodular.in");
    f >> A >> N;
    f.close();

    ofstream g("inversmodular.out");
    g << modularPow(A, phi(N) - 1, N);
    g.close();

    return 0;
}

int phi(int n)
{
    int result = n;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            result -= result / i;
        while (n % i == 0)
            n /= i;
    }

    if (n > 1)
        result -= result / n;

    return result;
}

int modularPow(long long base, long long exponent, long long mod)
{
    int result = 1;
    while (exponent)
    {
        if (exponent & 1)
            result = ((result % mod) * (base % mod)) % mod;
        base = ((base % mod) * (base % mod)) % mod;
        exponent >>= 1;
    }

    return result;
}