#include <bits/stdc++.h>

using namespace std;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

int a, n;

int gcd(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

void modInverse(int a, int mod){
	int x, y;
	int d = gcd(a, mod, x, y);

	if(d == 1){
		x = (x % mod + mod) % mod;
		cout << x << "\n";
	}
}

int main(){

	cin >> a >> n;
	modInverse(a, n);
}