#include <stdio.h>

long long inversmodular(long long N) {
    long long res = N;
    for(long long i = 2; i * i <= N; i ++) {
        if(N % i == 0) {
            while(N % i == 0) {
                N = N/i;
            }
            res = res - res/i;
        }
    }
    if (N > 1)
        res = res - res/N;
    return res;
}

long long exp_log(long long A, long long phi, long long N) {
    if (phi == 0)
        return 1;
    A = A % N;
    long long p = 1;
    while(phi > 0) {
        if(phi % 2 == 1)
            p = (p * A) % N;
        A = (A * A) % N;
        phi = phi/2;
    }
    return p;
}

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

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

    FILE *fout = NULL;
    fout = fopen("inversmodular.out", "w");
    fprintf(fout,"%lld", exp_log(A, phi-1, N));
    
    fclose(fin);
    fclose(fout);
    return 0;
}