#include <stdio.h>
using namespace std;
long long ridicare(long long baza, long long exp, long long n)
{
    long long rez=1;
    baza%=n;
    while(exp!=0)
    {
        if(exp%2==1)
        {
            rez*=baza%n;
            exp--;
        }
        else
        {
            baza=(baza*baza)%n;
            exp/=2;
        }
    }
    return rez%n;
}
int main ()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long a, n, phi, cn, f=2, p=0;
    bool prim=true;
    scanf("%lld%lld",&a,&n);
    phi=n;
    cn=n;
    while(f*f<=n)
    {
        p=0;
        while(n%f==0)
        {
            p++;
            n/=f;
            prim=false;
        }
        if(p)
        {
            phi/=f;
            phi*=(f-1);
        }
        f++;
    }
    if(n>1)
    {
        phi/=n;
        phi*=(n-1);
    }
    n=cn;
    if(prim)
        printf("%lld",ridicare(a,phi-1,n));
    else
        printf("%lld",ridicare(a,phi,n));
    return 0;
}