#include <fstream>

int phi(int num) {
    int copy;
    copy = num;
    for (int index = 2; copy > 1; index++) {
        if (!(copy % index)) {
            num /= index;
            num *= (index - 1);
            while (!(copy % index)) {
                copy /= index;
            }
        }
    }
    return num;
}

int put(int base, int pow, int mod) {
    int sav, ans, cnt;
    sav = base;
    ans = 1;
    cnt = 0;
    while (pow) {
        if ((pow & -pow) == 1 << cnt) {
            ans *= sav;
            ans %= mod;
            pow = pow & (pow - 1);
        }
        sav *= sav;
        sav %= mod;
        cnt++;
    }
    return ans;
}

int main() {
    std::ifstream fin("inversmodular.in");
    std::ofstream fout("inversmodular.out");
    int nra, nrb;
    fin >> nra >> nrb;
    fout << put(nra, phi(nrb) - 1, nrb);
}