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