#include <fstream>

using namespace std;

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

long long A,P;

long long pw(long long,long long);
int getPhi(int);
// getPhi(N) return-eaza indicatorul lui Euler pentru numarul N folosind formula de produs a lui Euler

int main() {
    in>>A>>P;

    int val = getPhi(P) - 1;
    out<<pw(A,val);

    in.close();out.close();
    return 0;
}

long long pw(long long x, long long e) {
    int prod = 1;
    while (e) {
        if (e%2) { prod = (prod * x) % P; }
        x = (x * x) % P;
        e >>= 1;
    }
    return prod;
}

int getPhi(int n) {
    int prod = n,
        x = n;
    for (int i=2;i*i<=n;++i) {
        if (x % i != 0) {
            continue;
        }
        while (x % i == 0) {x /= i;}
        prod = 1LL * prod * (i-1) / i;
    }
    if (x != 1) {
        prod = 1LL * prod * (x-1) / x;
    }

    return prod;
}