#include <cstdio>



long long n,m;

long long calc(long long nr)
{
    long long curent = nr;
    for(long long i = 2;i * i <= nr; i++)
    {
        if (!(nr % i))
        {
            while(!(nr % i))
                nr /= i;
            curent = (curent / i) * (i - 1);
        }
    }
        if (nr != 1)
            curent = curent / nr * (nr - 1);
    return curent;
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d %d",&n,&m);
    long long power = calc(m) - 1;
    long long nr = n;
    long long curent = 1;
    for(long long p = 1;p <= power;p <<= 1)
    {
        if (p & power)
            curent = (curent * nr) %m;
        nr = (nr * nr) % m;
    }
    printf("%d\n",curent);
}