#include <fstream>
#define MAX 2000000000
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long a, n;
/// inversul modular al lui 'a' modulo 'n' este a ^ [phi(n) - 1], deoarece a ^ phi(n) = 1 (modulo n)
long long Phi(long long nr)
{
    long long cur = nr;
    for(long long 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;
}
/// nmax - modulo
/// p - puterea
long long InversModular(long long nmax, long long p)
{
    long long x = 1;
    long long y = a%nmax;
    while(p > 0)
        if(p%2 == 0)
        {
            y = (y*y)%nmax;
            p /= 2;
        }
        else
        {
            x = (x*y)%nmax;
            p --;
        }
    return x;
}
int main ()
{
    f >> a >> n;
    g << InversModular(n, Phi(n) - 1);
    return 0;
}