#include <stdio.h>

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

	return p;
}

long long power2(long long p , long long q , long long n)
{
	printf("%lld %lld\n",p,q);
	if(q == 0) return 1;
	if(q == 1) return p;
	if(q%2 == 0) return power2((p*p)%n , q/2 , n)%n;
	return (p*power2((p*p)%n , (q-1)/2 , n))%n;
}

long long power(long long p , long long q , long long n)
{
	long long r = 1;
	
	while (q != 0) 
	{
        if (q % 2 == 1) 
		{    
            r = (r*p)%n;
            q--;
        }
		
        p = (p*p)%n;
        q = q/2;
    }

    return r%n;
}

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" , power2(a , phi(n)-1 , n));
	
	fclose(fout);
	
	return 0;
}