#include <fstream>

using namespace std;

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

long long eul(long long n)
{
    long long cnt = n - 1, i;
    for (i = 2; i * i < n; ++i)
        if (n % i == 0)
            cnt--;
    ++i;
    if (i * i == n) cnt--;
    return cnt;
}

long long mod;

long long lgput(long long a, long long b)
{
    long long p = 1;
    while (b)
    {
        if (b & 1)
        {
            p *= a;
            p %= mod;
            b--;
        }
        else
        {
            a *= a;
            a %= mod;
            b = b >> 1;
        }
    }
    return p;
}

int main()
{
    long long a, n;
    fin >> a >> n;
    long long phi = eul(n) - 1;
    mod = n;
    fout << lgput(a, phi) << "\n";
    return 0;

}