#include <stdio.h>

long long exp_by_squaring(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;
}

//phi(N) = N * product[(1 - 1/p)] for each prime factor p of N
long long euler_phi(long long n) {
    long long result = n;

    // try every divisor
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            result = result / p * (p - 1);

            while (n % p == 0) {
                n /= p;
            }
        }
    }

    if (n > 1) {
        result = result / n * (n - 1);
    }

    return result;
}

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

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

    long long phi = euler_phi(N);

    // A^(phi(N)-1) mod N
    fprintf(fout, "%lld\n", exp_by_squaring(A, phi - 1, N));

    fclose(fin);
    fclose(fout);
    return 0;
}