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

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

int a, k;

int Phi(int n)
{
    int f, e, 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 ExpoLog(int a, int n)
{
    int p = 1;
    while (n > 0)
    {
        if (n % 2 == 1) p = 1LL * p * a % k;
        n /= 2;
        a = 1LL * a * a % k;
    }
    return p;
}

int main()
{
    fin >> a >> k;
    fout << ExpoLog(a, Phi(k) - 1);
    return 0;
}