#include <fstream>
#include <iostream>

using namespace std;
long long int PN(long long int a)
{
    long long int i, copie;

    copie = a;

    for(i = 2; i * i <= a; i++)
    {
        if(a % i == 0)
        {
            while(a % i == 0)a /= i;
            copie = (copie / i) * (i - 1);
        }
    }

    if(a != 1)copie = (copie / a) * (a - 1);
    return copie;
}


long long int ridicarePutereLogaritmica(long long int baza, long long int p, long long int modulo)
{
    long long int putere = 1;

    while(p >= 1)
    {
        if(p % 2 == 1)putere = (putere * baza) % modulo;

        baza = baza * baza % modulo;
        p /= 2;
    }

    return putere;
}
int main()
{
    long long int a, n, inversModular, Pn;

    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");

    fin >> a >> n;

    Pn = PN(n);
    Pn--;

    inversModular = ridicarePutereLogaritmica(a, Pn, n);

    fout << inversModular;

    fin.close();
    fout.close();

    return 0;
}