#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");

ofstream fout("inversmodular.out");

long long eul(long long n)

{

long long r = n, d = 2;

while (n > 1)

{

if (n % d == 0)

{

r /= d;

r *= (d - 1);

while (n % d == 0)

n /= d;

}

++d;

if (d * d > n)

d = n;

}

return r;

}

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;

}