#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
bool isprim(int N) {
    for (int i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int A, N;
    cin >> A >> N;
    if (isprim(N)) {
        // cand N este prim
        // ne trebuie A ^ N-2
        int baza = A, exp = N-2;
        baza%= N;
        int r = 1;
        while (exp) {
            if (1 & exp) {
                r = (r * baza) % N;
            }
            baza = baza * baza % N;
            exp >>= 1;
        }
        // r este inversul modular
        cout << r;
    }


    fin.close();
    fout.close();
    return 0;
}