#include <fstream>
using namespace std;

ifstream in { "inversmodular.in" };
ofstream out { "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;
    in >> a >> mod;
    
    int64_t pow = Phi(mod) - 1;
    int64_t sol = 1;
    while (pow) {
        if (pow & 1) {
            --pow;
            sol = sol * a % mod;
        } else {
            pow /= 2;
            sol = sol * sol % mod;
        }
    }
    
    out << sol;
}