#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;
    for(d=2;d*d<=n;d++)
        if(n%d==0)
        {
            while(n%d==0)
            {
                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;
}