#include <bits/stdc++.h>

using namespace std;

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

int a, n;

long long inv(int x) {
	if(x <= 1) {
		return x;
	}
	return n - 1LL * n/x * inv(n%x) % n;
}

int main() {
	in >> a >> n;
	out << inv(a);

	return 0;
}