#include<fstream>
#include<cmath>
#include<cstring>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int nrprime(int lim)
{
    int sqr = (int)sqrt(lim);
    long long nr=lim;
    bool *isComposite = new bool[lim + 1];
    memset(isComposite, 0, sizeof(bool) * (lim + 1));
    for(int i=2;i<=sqr;i++)
        if(lim%i==0&&!isComposite[i]){
            nr*=i-1;
            nr/=i;
            for(int j=i*i;j<=lim;j+=i)
                isComposite[j]=true;
        }
    for(int i=sqr+1;i<=lim;i++)
    if(lim%i==0&&!isComposite[i]){nr*=i-1;nr/=i;}
    return nr;
}
int putere(int a,int b,int mod){
    int x=1,y=a;
    while(b>0){
        if(b%2==1){
            x=x*y;
            if(x>mod)x%=mod;
        }
        y=(y*y)%mod;
        if(y>mod)y%=mod;
        b/=2;
    }
    return x;
}
int main(){
    int a,n,d;
    fin>>a>>n;
    fout<<(putere(a,nrprime(n)-1,n))<<'\n';
    fin.close();
    fout.close();
    return 0;
}