#include <fstream>
using namespace std;
int n;
bool Prim (int x)
{
    if (x <= 1) return false;
    if (x % 2 == 0 && x != 2) return false;
    for (int i = 3; i * i <= x; i += 2)
        if (x % i == 0)
            return false;
    return true;
}
int Phi (int x)
{
    int f, phi;
    f = 2;
    phi = x;
    if (Prim(x)) return x - 1;
    while (f * f <= x && x > 0)
    {
        while (x % f == 0)
            x /= f;
        phi /= f;
        phi *= (f - 1);
        f++;
    }
    if (x > 1)
    {
        phi /= x;
        phi *= (x - 1);
    }
    return phi;
}
long long lgput (int a, int b)
{
    long long x = 1;
    while (b)
    {
        if (b & 1)
            x = 1LL * x * a % n;
        b /= 2;
        a = 1LL * a * a % n;
    }
    return x;
}
int main()
{
    int a;
    ifstream fin ("nc.in");
    ofstream fout ("nc.out");
    fin >> a >> n;
    fout << lgput(a, Phi(n) - 1) << "\n";
    fout.close();
    return 0;
}