#include <fstream>
using namespace std;

#define ll long long

ll exponentiation_by_sq(ll n, ll p, ll orig_n) {
    if (p == 0)
        return 1;
    if (p % 2 == 0)
        return exponentiation_by_sq(n * n % orig_n, p / 2, orig_n) ;
    if (p % 2 == 1) {
        return n * exponentiation_by_sq(n * n %orig_n, (p - 1) / 2, orig_n) % orig_n;
    }
    return 1;
}

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

    ll a, n;

    fin>>a>>n;

    fout<<exponentiation_by_sq(a, n - 2, n);

    return 0;
}