#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long a, n, x, y, i, dp, p;

long long phi(long long N)
{
    long long cn = N;
    for (i = 2; i*i <= N; i++)
    if (!(N%i))
    {
        while (!(N%i))
            N /= i;
        cn = (cn / i) * (i-1);
    }
    if (N > 1)
        cn = cn / N * (N-1);

    return cn;
}

int main()
{
    f >> a >> n;
    dp = phi(n)-1;
    long long rez = 1, nr = a;
    for (p = 1; p <= dp; p <<= 1)
    {
        if (p & dp)
            rez = (rez * nr) % n;
        nr = (nr * nr) % n;
    }
    g << rez;
    return 0;
}