#include <iostream>
#include <fstream>

using namespace std;

#define ll long long

void gcd_non_recursive(ll &x, ll &y, int &a, int b) {
    x = 0, y = 1;
    ll lastx = 1, lasty = 0, aux;
    while (b != 0) {
        ll q = a / b;
        ll r = a % b;
        a = b, b = r;
        aux = x, x = lastx - q * x, lastx = aux;
        aux = y, y = lasty - q * y, lasty = aux;
    }
    x = lastx;
    y = lasty;
}

int main() {
    ll x, y;
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    // int a = 1432, b = 123211;
    int a = 5, b = 7;
    fin >> a >> b;
    gcd_non_recursive(x, y, a, b);
    // cout << "GCD: " << a << ", x: " << x << ", y: " << y << endl;
    if (x <= 0)
        x += b;
    fout << x;
    return 0;
}

// ax + by = 1