#include<fstream>

using namespace std;

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

long long n, p;
bool da = 0;

long long euler(long long t) {
    long long d = 2, eu = t;

    while(d*d<=t) {
        da = 0;
        while(t%d == 0) {
            t /= d;
            da = 1;
        }
        eu = (da) ? eu * (d-1)/d : eu;
        d++;
    }

    if( t > 1) return eu * (t-1)/t;
    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;
}