#include <iostream>
#include <fstream>

using namespace std;
int mod;
int pwr(long long n,long long p){
    int sol=1;
    for(int i=0;((1<<i)<=p); ++i){
        if((1<<i) & p) sol = (1ll * n * sol) % mod;
        n = (1ll * n * n) % mod;
    }
    return sol;
}

long long int n,x,fi;
int main()
{
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    in >> x >> n;
    mod = n;
    fi = n;
    for(int i=2;1ll * i * i <= n;i++){
        if(!(n%i))
        {
           while (!(n%i)) n/=i;
           fi = fi - fi / i;
        }
    }
    if (n != 1) fi -= fi / n;

    int rasp = pwr(x,fi - 1);
    out << rasp;
    return 0;
}