#include <fstream>
using namespace std;

#define int long long

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

int Phi(int mod) {
    int sol = mod;
    for (int 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;
}

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

    int pow = Phi(mod) - 1;
    int sol = 1;
    for (; pow; pow /= 2) {
        if (pow % 2)
            sol = (sol * a) % mod;
        if (pow != 1)
            sol = (sol * sol) % mod;
    }

    cout << sol;
}