#include <fstream>

using namespace std;
long long fact[105],exp[105];
long long mod;
long long lgput(long long baza,long long put){
    long long rez=1;
    for(long long i=put;i>=1;i>>=1){
        if(i&1){
            rez*=baza;rez%=mod;
        }
        baza*=baza;baza%=mod;
    }
    return rez;
}
int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    long long a,n,phi=1,nr;fin>>a>>n;mod=n;
    long long d=2;int cnt=0,poz=1;
    while(n>1&&1LL*d*d<=n){
        cnt=0;
        while(n%d==0){
            cnt++;n/=d;
        }
        if(cnt>0){
            fact[poz]=d;exp[poz]=cnt;poz++;
        }
        d++;
    }
    if(n>1){
        fact[poz]=n;exp[poz]=1;poz++;
    }
    for(int i=1;i<poz;i++){
        nr=1;
        for(int j=1;j<exp[i];j++){
            nr*=fact[i];
        }
        nr*=(fact[i]-1);
        phi*=nr;
    }
    long long invers=lgput(a,phi-1);
    fout<<invers<<'\n';
    return 0;
}