#include <fstream>
using namespace std;

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

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;
    int64_t sol = 1;
    for (; pow; pow /= 2) {
        if (pow % 2)
            sol = (sol * a) % mod;
        if (pow != 1)
            sol = (sol * sol) % mod;
    }

    cout << sol;
}