#include <fstream>

using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

int a, n;

int fi (int n) {
    int f = n, d = 2;
    while (d * d <= n) {
        if (n % d == 0) {
            f /= d;
            f *= (d - 1);
            while (n % d == 0)
                n /= d;
        }
        d++;
    }
    if (n != 1) {
        f /= n;
        f *= (n - 1);
    }
    return f;
}

int putere (int a, int n, int mod) {
    int p = 1;
    while (n != 0) {
        int cif = n % 2;
        if (cif)
            p = 1LL * p * a % mod;
        a = 1ll * a * a % mod;
        n /= 2;
    }
    return p;
}

int main() {
    fin >> a >> n;
    int f = fi(n);
    fout << putere (a, f - 1, n);
    return 0;
}