#include <cstdio>
#include <algorithm>
using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

template<class T> pair<T, T> egcd(T a, T b) {
	pair<T, T> x(0, 1), y(1, 0), g(a, b);
	while (g.second != 0) {
		T q = g.first / g.second;
		g = pair<T, T> (g.second, g.first % g.second);
		x = pair<T, T> (x.second - q * x.first, x.first);
		y = pair<T, T> (y.second - q * y.first, y.first);
	}
	return pair<T, T> (x.second, y.second);
}

inline long long pow(long long a, long long b, long long mod) {
	long long ans = 1;
	while (b) {
		if (b & 1) {
			ans = (ans * a) % mod;
		}
		a = (a * a) % mod;
		b >>= 1;
	}
	return ans;
}

int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	long long n = next_int();
	long long p = next_int();
	printf("%lld\n", ((egcd(n, p).first % p) + p) % p);
	return 0;
}