#include <iostream>
#include <fstream>
using namespace std;

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

long long euler(long long b)
{
    long long x = b;
    for (long long d = 2; d * d <= b; d++)
    {
        if (b % d == 0)
        {
            while (b % d == 0) b /= d;
            x /= d;
            x *= (d - 1);
        }
    }
    if (b != 1)
    {
        x = x / b;
        x = x * (b - 1);
    }
    return x;
}

long long pow(long long b, long long p, long long mod)
{
    long long x = 1;
    while (p)
    {
        if (p & 1) x = (x * b) % mod;
        b = (b * b) % mod;
        p >>= 1;
    }
    return x;
}

int main()
{
    long long a, b, sol, p;
    in >> a >> b;
    p = euler(b) - 1;
    out << pow(a, p, b);
}