#include <fstream>
using namespace std;

ifstream I("inversmodular.in");
ofstream O("inversmodular.out");

long long FastPowMod(int n, int pow, int mod) {
    long long aa = n, result;
    for (result = 1; pow; pow = pow >> 1) {
        if (pow & 1) {
            result = (result * aa) % mod;
        }
        aa = (aa * aa) % mod;
    }
    return result;
}

int Phi(int N) {
    int Euler = N, f = 2, p;    //summoning the ghost of Euler to do my code
    while (f * f <= N) {
        p = 0;
        while (N % f == 0) {
            p++;
            N = N / f;
        }
        if (p > 0) {
            Euler = Euler / f * (f - 1);
        }
        f++;
    }
    if (N > 1) {
        Euler = Euler / N * (N - 1);
    }
    return Euler;   //Getting Euler's ghost out of the computer to not curse it
}

long long InversModular(int k, int N) {
    return FastPowMod(k, Phi(N) - 1, N);
}

int main(){

    int a, n;
    I >> a >> n;
    O << InversModular(a, n);

    I.close();
    O.close();
    return 0;
}