#include<fstream>
#include<cmath>
#include<cstring>
#include<bitset>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
bitset<50000>a;
bool prime(int x){
    int sqr=(int)sqrt(x);
    for(int i=2;i<=sqr;i++)
        if(x%i==0)return false;
    return true;
}
int nrprime(int lim)
{
    int sqr = (int)sqrt(lim);
    long long nr=lim;
    for(int p=2;p<=sqr;p++)
        if(lim%p==0&&!a[p]){
            nr*=p-1;
            nr/=p;
            for(int i=1;i*p<=sqr;i++)
                a[i*p]=1;
            if(prime(lim/p)){
                nr*=lim/p-1;
                nr/=lim/p;
            }
        }
    if(nr==lim)--nr;
    return nr;
}
int 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 putere2(int a,int b, int mod){
    int x=1;
    for(int i=1;i<=b;i++)
        x=(x*a)%mod;
    return x;
}
int main(){
    int a,n;
    fin>>a>>n;
    fout<<putere(a,nrprime(n)-1,n)<<'\n';
    fin.close();
    fout.close();
    return 0;
}