#include <stdio.h>

long long getphi(long long nr)
{
	long long cur = nr;
	
	for(long long i = 2;i * i <= nr; ++i)
	{
		if (nr % i == 0)
		{
			while(nr % i == 0)nr /= i;
			cur = (cur / i) * (i - 1);
		}
	}
	
	if (nr != 1) cur = cur / nr * (nr - 1);
	
	return cur;
}


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;
		}

	return p;
}

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