#include <fstream>

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

long long int put(long long int base, long long int pow, long long int mod) {
    long long int sav, ans, cnt;
    sav = base;
    ans = 1;
    cnt = 0;
    while (pow) {
        if ((pow & -pow) == (long long int)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");
    long long int nra, nrb;
    fin >> nra >> nrb;
    fout << put(nra, phi(nrb) - 1, nrb);
}