#include <bits/stdc++.h>
using namespace std;
#define MAX 20000000
int r[MAX],x[MAX],y[MAX],q[MAX];
//Determina inversul modular
int DVM(int a, int M){
	x[0]=1;x[1]=0;
	y[0]=0;y[1]=1;
	r[0]=a;r[1]=M;
	int i=1;
	while(r[i]){
		i++;
		q[i]=r[i-2]/r[i-1];
		r[i]=r[i-2]-q[i]*r[i-1];
		x[i]=x[i-2]-q[i]*x[i-1];
		y[i]=y[i-2]-q[i]*y[i-1];
	}
	return x[i-1];
}

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

int main(){
	int a,n;
	fin>>a>>n;
	fout<<DVM(a,n);
	return 0;
}