#include <stdio.h>
// INVERS MODULAR - metoda Euler
// formula: pentru fiecare factor prim p al lui N, inmultim cu (1 - 1/p)
// am luat formula direct din curs
long long phi(long long n) {
    long long rezultat = n;  // pornim de la n si scadem treptat
    long long p;

    for (p = 2; p * p <= n; p++) {  // mergem pana la sqrt(n), ca la factorizare
        if (n % p == 0) {
            while (n % p == 0) {
                n = n / p;  // scoatem toti factorii p
            }
            rezultat = rezultat - rezultat / p;    // din curs: result -= result / i  (adica result = result * (1 - 1/p))
        }
    }

    // daca mai ramane ceva dupa sqrt, acel rest e tot un factor prim
    if (n > 1) {
        rezultat = rezultat - rezultat / n;
    }

    return rezultat;
}

// ridicare la putere logaritmica, am luat-o de la exercitiul anterior
long long putere_log(long long baza, long long exp, long long mod) {
    long long p = 1;
    baza = baza % mod;

    while (exp > 0) {
        if (exp % 2 == 1) {
            p = p * baza % mod;
        }
        baza = baza * baza % mod;
        exp = exp / 2;
    }
    return p;
}

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

    if (fin == NULL) {
        printf("nu gasesc fisierul\n");
        return 1;
    }

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

    long long fn = phi(N);              // calculam phi(N)
    long long x  = putere_log(A, fn - 1, N);  // X = A^(phi(N)-1) mod N

    fprintf(fout, "%lld\n", x);

    fclose(fin);
    fclose(fout);

    return 0;
}