#include <fstream>

using namespace std;

int A, N;

int get(int v)
{
    int phi = v;
    for (int i = 2; i * i <= v; ++i)
    {
        if (v % i == 0)
        {
            v /= i;
            phi = (phi / i) * (i - 1);
        }

        i += (i != 2);
    }
    if (v != 1) phi = (phi / v) * (v - 1);
    return phi;
}
inline int dub(int x)
{
    return (x * x) % N;
}
inline int exp(int a, int b)
{
    if (b == 0) return 1;
    if (b % 2 == 0) return dub(exp(a, b / 2));
    return (a * dub(exp(a, b / 2))) % N;
}

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

    fin >> A >> N;
    fout << exp(A, get(N) - 1);

    fin.close();
    fout.close();
}