#include <fstream>

using namespace std;

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

long long mod;


long long exponentiation(long long b, long long e){
    long long a = b;
    long long rez = 1;
    for(long long i = 1; i <= e; (i <<= 1)){
        if(i & e){
            rez = (1LL * rez * a) % mod;
        }
        a = (1LL * a * a) % mod;
    }
    return rez % mod;
}

long long phi(long long nr){
    long long rez = nr;
    for(int i = 2; i * i <= nr; ++i){
        if(nr % i == 0){
            rez = rez * (i - 1) / i;
            while(nr % i == 0){
                nr /= i;
            }
        }
    }
    if(nr > 1){
        rez = rez * (nr - 1) / nr;
    }
    return rez;
}

void solve(){
    long long n;
    fin >> n >> mod;
    long long phimod = phi(mod);
    fout << exponentiation(n, phimod - 1);
}

int main()
{
    solve();
    return 0;
}