#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <queue>

using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

int A,N;
int getPhi(int);
int pw(int,int);

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

    int phi = getPhi(N);

    out<<pw(A,phi - 1)<<'\n';

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

int getPhi(int nr) {
    long long phi = nr;

    for (int i=2;i*i <= nr;++i) {
        if (nr % i != 0) {
            continue;
        }

        while (nr % i == 0) {
            nr /= i;
        }

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

    return phi;
}

int pw(int b,int e) {
    int res = 1;
    while (e) {
        if (e & 1) {
            res = (1LL * res * b) % N;
        }
        b = (1LL * b * b) % N;
        e >>= 1;
    }

    return res;
}