#include <cstdio>
#include <cmath>
using namespace std;
long long n;
bool Prim(int a)
{
    if(a==0||a==1||(a%2==0&&a>2))
        return false;
    else
        {
            int lim;
            lim=(int)sqrt((double)a);
            for(int d=3;d<=lim;++d)
                if(a%d==0)
                    return false;
            return true;
        }
}
int np(long long a)
{
    int s=2;
    for(int i =2;i<n;++i)
        if(a%i==0||i%a==0)
            ++s;
    return s;
}
long long rez(long long x, long long y) {

    if(y == 0)
        return 1;

    long long d = rez(x, y/2);

    if(y%2 == 0)
        return d*d%n;
    else
        return d*d%n*x%n;
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long a;
    int x;
    scanf("%lld%lld",&a,&n);
    if(Prim(n))
        printf("%lld\n",rez(a,n-2));
    else
        printf("%lld\n",rez(a,np(n)-1));
    return 0;
}