#include<cstdio>
long long n,m;
long long getphi(long long nr)
{
    long long sol=nr,i;
    for(i=2;i*i<=nr;++i)
        {
        if (nr%i==0)
            {
            while(nr%i==0)
              nr=nr/i;
            sol=(sol/i)*(i-1);
            }
        }
    if (nr!=1)
        sol=sol/nr*(nr-1);
    return sol;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long p;
    scanf("%lld%lld\n",&n,&m);
    long long put=getphi(m)-1;
    long long nr=n;
    long long 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;
}