#include <iostream>
#include <stdio.h>

using namespace std;

int getPhi(int nr);
int lgExp(int n, int mod, int exp);

int main()
{
    int n, a, phi, res;
    FILE *fin = fopen("inversmodular.in", "r");
    fscanf(fin, "%d%d", &a, &n);
    fclose(fin);

    phi = getPhi(n);
    res = lgExp(a, n, phi - 1);

    FILE *fout = fopen("inversmodular.out", "w");
    fprintf(fout, "%d", res);
    fclose(fout);

    return 0;
}


int getPhi(int nr) {
    int phi = nr;
    int d = 2;
    while (d * d <= nr) {
        if (nr % d == 0) {
            phi -= phi / d;
            while (nr % d == 0)
                nr /= d;
        }
        d++;
    }
    if (nr > 1)
        phi -= phi / nr;

    return phi;
}
int lgExp(int n, int mod, int exp) {
    int res = 1;
    while (exp) {
        if (exp & 1)
            res = ((long long)res * n) % mod;
        n = ((long long)n * n) % mod;
        exp >>= 1;
    }
    return res;
}