#include <bits/stdc++.h>
using namespace std;
///aproapeperm
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long A, N;

long long Phi(long long n)
{
    long long 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;
}
long long LogExpo(long long a, long long 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;
}