#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);
    int nr = 0;
    bool * isComposite = new bool[lim+1];
    memset(isComposite, 0, sizeof(bool)*(lim+1));
    for(int p = 2; p <= sqr; p++)
    {
        if(!isComposite[p]&&lim%p==0)
        {
            ++nr;
            for(int k = p*p; k <= lim; k+=p)
            isComposite[k] = true;
        }
    }
    for(int i = sqr+1; i <= lim; i++)
        if(!isComposite[i]) ++nr;
    delete[] isComposite;
    return nr+1;
}
long long putere(int a,int b,int mod){
    long long 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;
}