#include <fstream>
#include <iostream>

#define ll long long

using namespace std;

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

ll n,m;

//primeCount
ll PHI(ll nr) {
    ll phi = nr;
    for (ll i = 2; i * i <= nr; ++i) {
        if (nr % i == 0) {
            while (nr % i == 0)
                nr /= i;
            phi = (phi / i) * (i - 1);
        }
    }
    if (nr != 1)
        phi = phi / nr * (nr - 1);
    return phi;
}

int main() {
    fin >> n >> m;
    ll exponent = PHI(m) - 1;
    ll inverse = 1;

    //logPow
    for (ll pow = 1; pow <= exponent; pow <<= 1) {
        if (pow & exponent)
            inverse = (inverse * n) % m;
        n = (n * n) % m;
    }
    fout << inverse;

    return 0;
}