#include <fstream>
#include <vector>

using namespace std;

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

int a,n;

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

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

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