#include<fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long a, n;

long long ridicare_putere(long long x, long long y){

    long long r = 1;
    while(y){

        if(y%2)
            r = (r * x) % n;
        x = (x * x) % n;
        y /= 2;
    }
    return r;
}

void rezolvare(){

    f >> a >> n;
    g << ridicare_putere(a, n - 2);
}

long long main(){

    rezolvare();
    return 0;
}