#include<stdio.h>
#include<math.h>
long long power(long long a,long long m,long long k)
{
    long long r;
    for(r=1;m;m>>=1)
    {
        if(m&1) r=(r*a)%k;
        a=(a*a)%k;
    }
    return r;
}
long long phi(long long n)
{
    long long e,lim=(long long)sqrt((double)n),d,p=n;
    d=2;
    while(d<=lim && n>1)
    {
        e=0;
        while(n%d==0) {n=n/d;e++;}
        if(e) p=p/d*(d-1);
        d++;
    }
    if(n>1) p=p/n*(n-1);
    return p;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long n,a;
    scanf("%lld%lld",&a,&n);
    //a ^ (phi(n)-1)
    printf("%lld",power(a,phi(n)-1,n));
    return 0;
}