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