#include <fstream>

using namespace std;

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

int A, N;

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

    int phi = N, 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++;
            }

            phi = (phi / primeFactor) * (primeFactor - 1);
        }

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

    return phi;
}

int Power(int base, int exp)
{
    int ans = 1LL;
    int aux = 1LL * base % N;

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

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

    return ans;
}

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

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

    return 0;
}