#include<stdio.h>

#define maxPr 44725

FILE*f=fopen("inversmodular.in","r");
FILE*g=fopen("inversmodular.out","w");

int A,N,Pr[maxPr],pr; bool C[maxPr];

inline int ciur () {
	int i,j,nrp = 0;
	
	Pr[++nrp] = 2;
	
	for ( i = 3 ; i <= maxPr ; i += 2 ){
		if ( !C[i] ){
			++nrp;
			Pr[nrp] = i;
			for ( j = i + i + i ; j <= maxPr ; j += i + i ){
				C[j] = 1;
			}
		}
	}
	
	return nrp;
}

inline int lgput ( int a , int b ){
	
	int p = a, s = 1;
	
	while ( b ){
		
		if ( b & 1 ){
			s = ( s * p ) % N;
		}
		
		p = (p * p) % N; 
		b = b >> 1;
	}
	
	return s;
}

inline int phi ( int n ){
	int i,rez = 1,p;
	
	for ( i = 1 ; i <= pr && n > 1 && Pr[i] * Pr[i] <= n ; ++i ){
		
		if ( !(n % Pr[i]) ){
			rez = (rez * ( Pr[i] - 1 ) ) % N; p = 0;
			
			while ( !(n % Pr[i]) ){
				n /= Pr[i];
				++p;
			}
			
			rez = (rez * lgput(Pr[i],p-1) ) % N;
		}
		
	}
	
	if ( n > 1 ){
		rez = (rez * (n-1) ) % N;
	}
	
	return rez;
}

int main () {
	
	fscanf(f,"%d %d",&A,&N);
	
	pr = ciur();
	
	fprintf(g,"%d\n", lgput(A,phi(N)-1) );
	
	fclose(f);
	fclose(g);
	
	return 0;
}