#include <stdio.h>

long long phi(long long n)
{
	long long p = n;
	long long d = 2;
	
	while(n != 1)
	{
		if(n % d == 0)
		{
			p = p*(d-1)/d;
			while(n % d == 0)
				n = n/d;
		}
		
		d++;
	}

	return p;
}

long long power(long long a , long long n)
{
	if(n == 0) return 1;
	if(n == 1) return a;
	if(n % 2 == 0) return power(a*a , n/2);
	return a*power(a*a , (n-1)/2);
}		

int main()
{
	FILE *fin = fopen("inversmodular.in" , "r");
	
	long long a , n;
	
	fscanf(fin , "%lld %lld" , &a , &n);
	
	fclose(fin);
	
	FILE *fout = fopen("inversmodular.out" , "w");
	
	fprintf(fout , "%lld" , power(a , phi(n)-1) % n);
	
	fclose(fout);
	
	return 0;
}