#include<fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long phi(long long n) {
    long long result = n;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
        result -= result / i;
        }
    }
    if (n > 1)
    result -= result / n;
    return result;
}
long long logridicare(long long a, long long k)
{
    if(k==0)
        return 1;
    if(k%2==0)
        return logridicare(a*a,k/2);
    else
        return a*logridicare(a*a,k/2);
}
int main(void)
{
    long long A,N;
    f>>A>>N;
    g<<logridicare(A,phi(N)-1)%N;

    return 0;
}