#include <fstream>

using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
long long a, n, putere, nr, r;
long long fi(long long n)
{
    long long aux=n, d=2, nr=1, p;
    while(d*d<=aux)
    {
        if(aux%d==0)
        {
            p=1;
            while(aux%d==0)
            {
                p=p*d;
                aux=aux/d;
            }
            p=p/d;
            nr=nr*p*(d-1);
        }
        d++;
    }
    if(aux!=0)
        nr*=(aux-1);
    return nr;
}
int main()
{
    fin >> a >> n;
    putere=fi(n)-1;
    nr=a;
    r=1;
    while(putere!=0)
    {
        if(putere%2==1)
            r=(r*nr)%n;
        nr=(nr*nr)%n;
        putere=putere/2;
    }
    fout << r;
    return 0;
}