#include <iostream>
#include <fstream>
using namespace std;

int a, n, y = 0, p, mod;

//n^p        % mod

long long solve(int exponent) {
    int jumatate = exponent / 2;

    if(exponent == 0) return 1;
    if(exponent == 1) return (n % mod);

    long long sol;
    sol = (solve(jumatate) * solve(jumatate)) % mod;
    if(exponent % 2 == 1) sol = (sol * n) % mod;

    return sol % mod;
}

int main() {
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");

    f>>n>>p;

    mod = p;

    y = solve(p-2);

    g<<y<<"\n";
    cout<<y<<"\n";

    return 0;
}