#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long long k,i,m,x,j,ct,phi;
long long ggt(long long a,long long b)
{
    if(!b)
        return a;
    return ggt(b,a%b);
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&x,&m);
    for(k=2;k<=sqrt(m);k++)
    {
        if(m%k==0)
            ct+=2;
        if(k==sqrt(m)&&m%k==0)
            ct--;
    }
    if(ct==0)
        phi=m-1;
    else
    {
        for(k=1,phi=m-1;k<=m-1;k++)
        {
            if(ggt(k,m)!=1)
                phi--;
        }
    }
    for(k=phi-1,j=1,i=x;k!=1;)
    {
        if(k%2==0)
        {
            k/=2;
            i*=i;
            i%=m;
        }
        else
        {
            k--;
            j*=i;
            j%=m;
        }
    }
    printf("%lld\n",j*i%m);
    return 0;
}