#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;

    for(d=2; d*d<=t; d++) {
        if(t%d == 0)
            break;
    }
    if(d*d>t) return t-1;
    d = 2;

    while(t) {
        if(t%d == 0) {
            eu = eu * (d-1) / d;
        }
        while(t%d == 0) {
            t /= d;
        }
        d++;
    }
    return eu;
}

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

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