#include <bits/stdc++.h>

#define llg long long

namespace maths {
    void euclid(llg A, llg B, llg &X, llg &Y) {
        if (B == 0) {
            Y = 0, X = 1;
            return;
        }   euclid(B, A%B, X, Y);
        llg aux = Y; Y = X - (A/B)*Y; X = aux;
    }

    llg invmod(llg A, llg MOD) {
        llg temp, inv;
        euclid(A, MOD, inv, temp);
        return (inv+MOD)%MOD;
    }
}

llg A, N;

std::ifstream input ("inversmodular.in");
std::ofstream output("inversmodular.out");

void readInput() {
    input >> A >> N;
}

void solveInput() {
    output << maths::invmod(A, N);
}

int main()
{
    readInput();
    solveInput();

    return 0;
}