#include <fstream>

#define LL long long
using namespace std;

ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

LL a, n;

inline LL get_phi(LL nr) {
    LL phi = nr;

    for(LL i = 2; i * i <= nr; ++i) {
        if(nr % i == 0) {
            while(nr % i == 0) {
                nr /= i;
            }

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

    if(nr - 1) {
        phi = phi / nr * (nr - 1);
    }

    return phi;
}

inline LL lgpow(LL nr, LL exp) {
    if(exp == 1) {
        return nr % n;
    }

    if(exp % 2 == 0) {
        LL half = lgpow(nr, exp / 2) % n;
        return half * half;
    }
    else {
        return lgpow(nr, exp - 1) * nr % n;
    }
}

int main() {
    cin >> a >> n;
    LL phi = get_phi(n) - 1;
    cout << lgpow(a, phi);
    return 0;
}