#include <fstream>

using namespace std;

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

int mod;

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

int phi(int nr){
    int rez = nr;
    if(nr % 2 == 0){
        while(nr % 2 == 0){
            nr /= 2;
        }
        rez /= 2;
    }
    int d = 3;
    while(nr > 1){
        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(){
    int n;
    fin >> n >> mod;
    int phimod = phi(mod);
    fout << exponentiation(n, phimod - 1);
}

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