#include <iostream>
using namespace std;

long long modinv(long long a, long long n) {
    long long x0 = 1, x1 = 0;
    long long a0 = a, n0 = n;

    while (n0) {
        long long q = a0 / n0;
        long long t = a0 - q * n0;
        a0 = n0;
        n0 = t;

        t = x0 - q * x1;
        x0 = x1;
        x1 = t;
    }

    if (x0 < 0) x0 += n;
    return x0;
}

int main() {
    long long a, n;
    cin >> a >> n;
    cout << modinv(a, n);
    return 0;
}