#include <stdio.h>
#include <stdlib.h>
#define int long long
int m;
int exponent(int a,int b){
    if(b==0) return 1;
    if(b==1) return a%m;
    if((a&1)) return ((a%m)*(exponent(a,b-1)%m))%m;
    else{
        int x=exponent(a,b>>1)%m;
        return ((x%m)*(x%m))%m;
    };
};
int phi(int n){
    int a=n,d=2;
    while(n>1){
        if(n%d==0){
            a=a/d*(d-1);
            while(n%d==0)n/=d;
        };
        d++;
        if(d*d>n) break;
    };
    return a;
};
signed main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int x;
    scanf("%lld%lld",&x,&m);
    printf("%lld",exponent(x,phi(m)-2)%m);
    
    return 0;
}