#include<cstdio>
using namespace std;
void exgcd(int a,int b,int &x,int &y){
	if(b==0){x=1,y=0;return;}
	exgcd(b,a%b,y,x);
	y-=(a/b)*x;
}
int get_inv(int a,int p){
	int x=1,y=0;
	exgcd(a,p,x,y);//x=a_inv,a*a_inv+p*y=1
	return (x%p+p)%p;
}
int a,p;
int main(){
	scanf("%d%d",&a,&p);
	printf("%d",get_inv(a,p));
}