#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("avx") // sse4, avx, avx2
#pragma GCC optimize ("fast-math")
using namespace std;

void ExtGcd(int a, int b, int& x, int& y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return;
    }
    
    int aux_x, aux_y;
    ExtGcd(b, a % b, aux_x, aux_y);
    x = aux_y;
    y = aux_x - (a / b) * aux_y;
}

int main() {
    #ifdef INFOARENA
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    #endif
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int a, mod;
    cin >> a >> mod;
    
    int x, y;
    ExtGcd(a, mod, x, y);
    
    if(x < 0)
        x += mod;
        
    cout << x << endl;
}