#include<cstdio>
using namespace std;
long long a,n,e=1,d,inv=1,i,N;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&a,&n);
    N=n;
    if(!(n%2))
    {
        while(!(n%2)) {n/=2;e*=2;}
        e/=2;
    }
    for(d=3;d*d<=n;d+=2)
    {
        if(!(n%d))
        {
            while(!(n%d)) {n/=d;e*=d;}
            e/=d;e*=d-1;
        }
    }
    if(n>1) e*=n-1;
    e--;
    /*for(i=0;(1<<i)<=e;i++)
    {
        if((1<<i)&e) inv=(inv*a)%N;
        a=(a*a)%N;
    }*/
    printf("%lld\n",inv);
    return 0;
}