#include <bits/stdc++.h>

using namespace std;

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

int a, n;

int gcd(long long a, long long b, long long &x, long long &y) {
    x = 1, y = 0;
    long long x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        long long 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){
	long long x, y;
	int d = gcd(1LL * a, 1LL * mod, x, y);
	if(d == 1) {
		x = (x % mod + mod) % mod;
		g << x << "\n";
	}
}

int main(){

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