#include <fstream>
using namespace std;

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

long long phi(long long n) {
    long long fi = n;
    if (n % 2 == 0) {
        fi /= 2;
        while (n % 2 == 0) {
            n /= 2;
        }
    }
    for (int d = 3; d * d <= n; d += 2) {
        if (n % d == 0) {
            fi = fi / d * (d - 1);
            while (n % d == 0) {
                n /= d;
            }
        }
    }
    if (n > 1) {
        fi = fi / n * (n - 1);
    }
    return fi;
}

long long exponentiere(long long a, long long b, long long MOD) {
    if (b == 0) {
        return 1;
    }
    if (b % 2) {
        return exponentiere(a * a % MOD, b / 2, MOD) * a % MOD;
    }
    return exponentiere(a * a % MOD, b / 2, MOD) % MOD;
}

long long invers_modular(long long a, long long n) {
    long long fi = phi(n); // n - 1 daca n este prim
    return exponentiere(a, fi - 1, n);
}

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

    fout << invers_modular(a, n);
    return 0;
}