#include <bits/stdc++.h>
using namespace std;
const string FNAME = "inversmodular";
ifstream fin(FNAME + ".in");
ofstream fout(FNAME + ".out");
using LL = long long;
LL a, n;

LL getPhi(LL n) {
    if (n == 0) {
        return 1;
    }
    LL phi = n;
    for (LL f = 2; f * f <= n; f++) {
        if (n % f != 0) {
            continue;
        }
        while (n % f == 0) {
            n /= f;
        }
        phi *= 1LL * (1 - (1.0 / f));
    }
    if (n > 1) {
        phi -= phi / n;
    }
    return phi;
}

LL lgpow(LL b, LL p) {
    LL ans = 1;
    while (p) {
        if (p % 2) {
            ans = (1LL * ans * b) % n;
        }
        b = (1LL * b * b) % n;
        p /= 2;
    }
    return ans;
}

int main() {
    fin >> a >> n;
    LL phi = getPhi(n);
    fout << lgpow(a, phi - 1) << endl;
    fout.close();
    return 0;
}