#include<cstdio>
using namespace std;
long long n,m,put,nr,crt,p;
long long getphi(long long nr)
{
    long long i,cur=nr;
    for(i=2;i*i<=nr;i++)

        if (nr%i==0)
        {
            while(nr%i==0)
            nr/=i;
            cur=(cur/i)*(i-1);
        }
        if(nr!=1)
            cur=cur/nr*(nr-1);
    return cur;
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld %lld\n",&n,&m);
    put = getphi(m) - 1;
    nr = n;
    crt = 1;
    for( p = 1;p <= put;p <<= 1)
    {
        if (p & put) crt = (crt * nr) % m;
        nr = (nr * nr) % m;
    }
    printf("%lld\n",crt);
    return 0;
}