#include <fstream>

using namespace std;

ifstream cin ("inversmodular.in");
ofstream cout ("inversmodular.out");

int n, a;

int phi(int n)
{
    int e = n, d = 2;
    while (d * d <= n)
    {
        if (n % d == 0)
        {
            e = e / d * (d - 1);
            while (n % d == 0)
                n /= d;
        }
        ++d;
    }
    if (n > 1)
        e = e / n * (n - 1);
    return e;
}
int p (int a, int b, int mod)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res *= a, res %= mod;
        a *= a % mod;
        a %= mod;
        b >>= 1;

    }
    return res;
}
int main()
{
    cin >> a >> n;
    cout << p (a, phi(n) - 1, n)<< '\n';

}