#include <stdio.h>

int phi(int n) {
    int rez = n;
    int copy = n;
    for (int d = 2; d * d <= copy; d++) {
        if (copy % d == 0) {
            while (copy % d == 0) {
                copy /= d;
            }
            rez = rez - rez / d;
        }
    }
    if (copy > 1)
        rez = rez - rez / copy;
    return rez;
}

long long exp_long(long long a, long long p, int n) {
    long long rez = 1;
    a = a % n;
    while (p > 0) {
        if (p % 2 == 1)
            rez = (rez * a) % n;
        a = (a * a) % n;
        p /= 2;
    }
    return rez;
}

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

    int a, n;
    fscanf(fin, "%d %d", &a, &n);
    fclose(fin);

    int p = phi(n) - 1;
    long long rez = exp_long(a, p, n);

    fprintf(fout, "%lld\n", rez);
    fclose(fout);

    return 0;
}