#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");


int A, N, inv;


long long lgput(long long N, long long K, long long MOD) {
    if (K == 0) {
        return 1;
    }

    long long M = 1;
    while (K > 1) {
        if (K % 2 == 0) {
            K /= 2;
            N = (N*N) % MOD;
        } else {
            --K;
           M = (M*N) % MOD;
        }
    }

    return (M*N) % MOD;
}
int invers(int A, int N) {
    return lgput(A, N - 2, N);
}
int main() {
    f >> A >> N;
    inv = invers(A, N);
    g << inv << '\n';

    f.close();
    g.close();
    return 0;
}