#include <iostream>

int mod;
int expRapida(int a, int b) {
    int rez;
    rez = 1;
    while (b > 0) {
        if (b % 2 > 0) {
            rez = (long long)rez * a % mod;
        }
        a = (long long)a * a % mod;
        b /= 2;
    }
    return rez;
}
int main()
{
    FILE *fin, *fout;
    int a, n, phi, d;
    fin = fopen("inversmodular.in", "r");
    fscanf(fin, "%d%d", &a, &n);
    fclose(fin);
    mod = n;
    d = 2;
    phi = n;
    while (d * d <= n) {
        if (n % d == 0) {
            phi = phi / d * (d - 1);
            while (n % d == 0) {
                n /= d;
            }
        }
        d++;
    }
    if (n > 1) {
        phi = phi / n * (n - 1);
    }
    fout = fopen("inversmodular.out", "w");
    fprintf(fout, "%d\n", expRapida(a, phi - 1));
    fclose(fout);
    return 0;
}