#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;

void inverse_modular(ll a,ll b){
	ll x0 = 1,y0 = 0,x1 = 0,y1 = 1,cb = b;
	while(b){
		ll x,y;
		ll q = a / b;
		ll r = a % b;
		a = b;
		b = r;
		x = x0 - q * x1;
		y = y0 - q * y1;
		x0 = x1; y0 = y1;
		x1 = x; y1 = y;
	}
	
	printf("%lld\n",(x0 + cb) % cb);
}

int main(){
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	ll a,b;
	scanf("%lld%lld",&a,&b);
	inverse_modular(a,b);
	return 0;
}