#include <fstream>

using namespace std;

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

long long eul(long long n)
{
    long long cnt = n, d = 2;
    while (n > 1)
    {
        if (n % d == 0)
        {
            cnt /= d;
            cnt *= d - 1;
            while (n % d == 0)
                n /= d;
        }
        ++d;
        if (d * d > n)
            d = n;
    }
    return cnt;
}

long long lgput(long long a, long long b, long long mod)
{
    long long res = 1;
    while (b)
    {
        if (b % 2)
        {
            res *= a;
            res %= mod;
        }
        a *= a;
        a %= mod;
        b /= 2;
    }
    return res;
}

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