#include <fstream>

using namespace std;

int GetPhi(int x)
{
    int ans = x, xx = x;

    if(x % 2 == 0)
    {
        ans /= 2;
        while(x % 2 == 0)
            x /= 2;
    }

    for(int i = 3; i * i <= xx; i += 2)
        if(xx % i == 0)
        {
            ans = (ans / i) * (i - 1);

            while(x % i == 0)
                x /= i;
        }

    if(x)
        ans = (ans / x) * (x - 1);

    return ans;
}

int Power(int base, int exp, int mod)
{
    int sol = 1;
    int aux = base % mod;

    for(long long i = 1; i <= exp; i <<= 1)
    {
        if(i & exp)
            sol = 1LL * sol * aux % mod;

        aux = 1LL * aux * aux % mod;
    }

    return sol;
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int A, N;

    fin >> A >> N;

    int phi = GetPhi(N);
    fout << Power(A, phi - 1, N);

    return 0;
}