#include <fstream>

using namespace std;

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

int64_t phi(int64_t target){
    int phi=target;
    for(int i=2;1LL*i*i<=target;++i)
        if(target%i==0){
            phi=(phi/i)*(i-1);
            for(;target%i==0;target/=i);
        }
    if(target>1) phi=(phi/target)*(target-1);
    return phi;
}

int64_t lgput(int64_t base,int64_t exponent,int64_t mod){
    int64_t x=1;
    for (;exponent;exponent>>=1){
        if (exponent&1)
            x=(1LL*x*base)%mod;
        base=(1LL*base*base)%mod;
    }
    return x;
}

int main()
{
    int64_t a,n;
    f>>a>>n;
    t<<lgput(a,phi(n)-1,n);
    return 0;
}