#include <stdio.h>
#include <stdlib.h>
long long a,n,x,y;

long long pow(long long e){
    long long temp;

    if(e==1){
        return a;
    }

    if(e%2==1){
        return pow(e-1)*a%n;
    }else{
        temp=pow(e/2)%n;
        return temp*temp%n;
    }
}
int main(){
    long long d,t;
    long long fi;

    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    scanf("%d%d",&a,&n);

    fi=n;
    t=n;
    for(d=2;d*d<=n;d++){
        if(n%d==0){
            fi=fi*(d-1)/d;
            while(n%d==0){
                n/=d;
            }
        }
    }
    if(n!=1){
        fi=fi*(n-1)/n;
    }
    n=t;
    printf("%lld",pow(fi-1)%n);
    return 0;
}