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