#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(lim%p==0){
            isComposite[p] = true;
            for(int k = p*2; k <= lim; k+=p)
            isComposite[k] = true;
        }
    }
    for(int i = 1; i < lim; i++)
        if(!isComposite[i])
            ++nr;
    delete[] isComposite;
    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;
    d=nrprime(n);
    //fout<<d<<'\n';
    fout<<(putere(a,d-1,n))<<'\n';
    fin.close();
    fout.close();
    return 0;
}