#include <fstream>
using namespace std;

ifstream cin{"inversmodular.in"};
ofstream cout{"inversmodular.out"};

int64_t putere(int64_t bz, int64_t exp, int64_t mod) {
    if (exp == 1)
        return bz % mod;

    if (exp % 2) {
        return (bz * putere(bz, exp - 1, mod)) % mod;
    } else {
        int64_t x = putere(bz, exp / 2, mod) % mod;
        return x * x % mod;
    }
}

int64_t Phi(int64_t mod) {
    int64_t sol = mod;
    for (int64_t i = 2; i * i <= mod; ++i)
        if (mod % i == 0) {
            do
                mod /= i;
            while (mod % i == 0);

            sol = sol / i * (i - 1);
        }

    if (mod != 1)
        sol = sol / mod * (mod - 1);

    return sol;
}

int main() {
    int64_t a, mod;
    cin >> a >> mod;

    int64_t pow = Phi(mod) - 1;

    cout << putere(a, pow, mod);
}