#include <iostream>

using namespace std;

pair<int, int> euclidExtins(int a, int b){
    if(b != 0){
        auto x = euclidExtins(b, a % b);
        return {x.second, x.first - (a / b) * x.second};
    }
    else{
        return {1, 0};
    }
};

int main() {
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    int n, p;
    scanf("%d %d", &n, &p);

    auto x = euclidExtins(n, p);

    while(x.first < 0){
        x.first += p;
    }

    printf("%d", x.first);

    return 0;
}