#include <fstream>

using namespace std;

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

long long A, N;

long long GetPhi(int x)
{
    if(x == 0 || x == 1)
        return 1;

    long long phi = 1, xx = x;

    for(int i = 2; i * i <= xx; i++)
        if(xx % i == 0)
        {
            int primeFactor = i;
            int pow = 0;

            while(x % primeFactor == 0)
            {
                x /= primeFactor;
                pow++;

                if(pow == 1)
                    phi *= (primeFactor - 1);
                else
                    phi *= primeFactor;
            }
        }

    if(x)
        phi *= (x - 1);

    return phi;
}

long long Power(long long base, long long exp)
{
    long long ans = 1;
    long long aux = base;

    for(int i = 1; i <= exp; i <<= 1)
    {
        if(i & exp)
            ans = ans * aux, ans %= N;

        aux = aux * aux, aux %= N;
    }

    return ans;
}

int main()
{
    fin >> A >> N;

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

    return 0;
}