#include <fstream>
#include <vector>

using namespace std;

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

int a,n;

int phi(int64_t target){
    int64_t res=n;
    vector <int> primes;
    for (int i=2;i*i<=n;++i){
        if (n%i==0)
            primes.push_back(i);
        while (n%i==0)
            n/=i;
    }
    for(auto prim:primes)
        res-=res/prim;
    if(n>1)
        res-=res/n;
    return res;
}

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

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