#include <bits/stdc++.h>
using namespace std;


int N, M;

void euclidExtins(const int a, const int b, int& x1, int& y1) {
    if (b == 0) {
        x1 = 1;
        y1 = 1;
        return;
    }

    int x2, y2;

    euclidExtins(b, a % b, x2, y2);

    x1 = y2;
    y1 = (x2 - a / b * y2) % M;
}

int inversModular(const int A) {
    int x1, y1;

    euclidExtins(A, M, x1, y1);

    if(x1 < 0)
        x1 += M;

    return x1;
}

int main() {
    freopen("inversmodular.in",  "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    cin >> N >> M;
    cout << inversModular(N);
}