#include<stdio.h>
long long n;
long long r ( long long a , long long b){
    long long p=1;
    while(b!=0){
        if(b%2==1){
            p=(p%n)*a;
            b--;
        }
        a=(a*a)%n;
        b=b/2;
    }
    return (p%n);
}

int main(){
    long long i,a1,putere,copie,x;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%I64d",&a1);
    scanf("%I64d",&n);
    putere=n;copie=n;
    for(i=2;i*i<=n;i++)
        if(n%i==0){
            putere=putere/i;
            putere=putere*(i-1);
            while(n%i==0)
                n/=i;
        }
    if(n!=1){
        putere=putere/n;
        putere=putere*(n-1);
    }
    n=copie;
    a1=a1%copie;
    x=r(a1,putere-1);
    printf("%I64d",x);
    return 0;
}