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