#include <iostream>
#include <fstream>

#define ull unsigned long long

using namespace std;

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

ull phi(ull n);
ull exp(ull N, ull P);

unsigned MOD;

int main() {
    unsigned A;
    fin >> A >> MOD;

    cout<<exp(A, phi(MOD) - 1) % MOD;

    return 0;
}

ull exp(ull N, ull P) {
    if (P == 0)
        return 1;

    if (P % 2)
        return N * exp((N * N) % MOD, (P - 1) / 2) % MOD;

    return exp((N * N) % MOD, P / 2);
}

ull phi(ull n) {
    ull r = n;

    for (ull i = 2; i * i <= n; ++i) {
        if (n % i)
            continue;

        while (n % i == 0)
            n /= i;

        r -= r / i;
    }

    if (n > 1)
        r -= r / n;

    return r;
}