#include<iostream>
#include<fstream>
#define LL long long
using namespace std;
LL N,M;
LL getphi(LL nr)
{
    LL cur = nr;
    for(LL 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()
{
    fstream f("inversmodular.in",ios::in);
    fstream g("inversmodular.out",ios::out);
    f>>N>>M;
        LL put = getphi(M) - 1;
    LL nr = N;
    LL crt = 1;
    for(LL p = 1;p <= put;p <<= 1)
    {
        if (p & put) crt = (crt * nr) % M;
        nr = (nr * nr) % M;
    }
    g<<crt;
    return 0;
}