#include <bits/stdc++.h>
using namespace std;

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

int A, N;

int Phi(int n)
{
    int f, e, phi;
    phi = n;
    for (f = 2; f * f < n; f++)
    {
        e = 0;
        while (n % f == 0)
        {
            e++;
            n /= f;
        }
        if (e > 0)phi = 1LL * phi * (f - 1) / f;
    }
    if (n > 1)phi = 1LL * phi * (n - 1) / n;
    return phi;
}
int LogExpo(int a, int b)
{
    int P = 1;
    while (b > 0)
    {
        if (b % 2 == 1)P = 1LL * P * a % N;
        b /= 2;
        a = 1LL * a * a % N;
    }
    return P;
}

int main()
{
    fin >> A >> N;
    fout << LogExpo(A, Phi(N) - 1);
    return 0;
}