#include<fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long n, p;

long long euler(long long t) {
    long long d = 2, eu = t;
    while(d*d <= t) {
        if(t%d == 0) {
            eu = eu * (d-1) / d;
        }
        while(t%d == 0) {
            t /= d;
        }
        d++;
    }
    return eu*(t-1)/t;
}

long long rez;
inline long long put(const long long &n, const long long &e) {
    if(e == 0) return 1;
    if(e%2==0) {
        return put((n*n)%p, e/2)%p;
    }
    else {
        return (n*put(n, e-1))%p;
    }
}

int main() {
    fin>>n>>p;
    long long EU = euler(p);
    fout<<put(n, EU-1);
    //fout<<put(2, 5);
    return 0;
}