#include<cstdio>
using namespace std;
long long mod;
long long ridic_la_putere(long long baza,long long exp){
    long long rez=1;
    while(exp!=0)
        if(exp%2==1){
            rez=rez*baza;
            exp--;
            rez%=mod;
        }
        else{
            baza=baza*baza;
            baza%=mod;
            exp/=2;
        }
    return rez;
}
long long phi(int nr){
    long long i,rez=nr;
    for(i=2;i*i<=nr;i++)
        if(nr%i==0){
            while(nr%i==0)
                nr/=i;
            rez=(rez/i)*(i-1);
        }
    if(nr!=1)
        rez=(rez/nr)*(nr-1);
    return rez;
}
int main(){
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long a,n,exp;
    scanf("%lld%lld",&a,&n);
    mod=n;
    exp=phi(n)-1;
    printf("%lld",ridic_la_putere(a,exp));
    return 0;
}