#include <stdio.h>

long long phiFunction(long long n) {
    long long result = n;
    for (long long d = 2; d * d <= n; ++d) {
        if (n % d == 0) {
            result = result / d * (d-1);
            while (n % d == 0)
                n /= d;
        }
    }
    if (n > 1)
        result = result / n * (n - 1);
    return result;
}

long long fastExonentiation(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int main() {
    FILE *in = fopen("inversmodular.in", "r");
    FILE *out = fopen("inversmodular.out", "w");

    if (!in || !out) return 1;

    long long A, N;
    fscanf(in, "%lld %lld", &A, &N);

    long long inverse = fastExonentiation(A, phiFunction(N) - 1, N);
    fprintf(out, "%lld\n", inverse);

    fclose(in);
    fclose(out);
    return 0;
}