#include <bits/stdc++.h>

using namespace std;

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


long long Phi(long long n) {
    long long sol = n;

    for (long long i = 2; i * i <= n; i++)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;

            sol = (sol / i) * (i - 1);
        }

    if (n != 1)
        sol = (sol / n) * (n - 1);

    return sol;
}

long long lgput(int a, int p, int MOD) {
    int r = 1;
    while(p) {
        if (p % 2)
            r = 1LL * a * r % MOD;

        p /= 2;

        a = 1LL * a * a % MOD;
    }

    return r;
}

int main() {
    long long a, n;
    fin >> a >> n;

    long long p = Phi(n) - 1;

    fout << lgput(a, p, n) << '\n';;
    return 0;
}