#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long int a, n;

long long int getPhi(long long int x) {
    long long int answer = x;

    for (int i = 2; i * i <= x; i++) {

        if (x % i == 0) {

            answer = answer / i * (i - 1);

            while (x % i == 0)
                x = x / i;
        }
    }

    if (x > 1)
        answer = answer / x * (x - 1);

    return answer;
}

long long int getPower(long long int a, long long int power) {

    if (power == 1)
        return a % n;

    long long int logPower = getPower(a, power / 2);

    if (power % 2 == 0)
        return (logPower * logPower) % n;

    return ((logPower * logPower) % n ) * a % n;
}

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

    long long int phi = getPhi(n);

    g << getPower(a, phi - 1) << "\n";

    return 0;
}