#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;
    if(nr % 2 == 0){
        while(nr % 2 == 0){
            nr /= 2;
        }
        rez /= 2;
    }
    long long d = 3;
    while(d * d <= nr){
        if(nr % d == 0){
            rez = rez * (d - 1) / d;
            while(nr % d == 0){
                nr /= d;
            }
        }
        d += 2;
    }
    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;
}