#include <fstream>
#include <cmath>

#define ll long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
ll a, n;

ll pow(ll a, ll p)
{
    if(p == 1)
        return a % n;

    ll rez = pow(a, p / 2);
    rez = rez * rez % n;
    if(p % 2 == 0)
        return rez;
    else
        return rez * a % n;
}

int main()
{
    fin >> a >> n;

    ll sqrtN = sqrt(n);
    ll nr = n - 1;
    for(ll i = 2; i < sqrtN; i ++)
        if(n % i == 0)
            nr -= 2;
    if(n % sqrtN == 0)
        nr --;

    fout << pow(a, nr - 1);
    return 0;
}