#include<stdio.h>

int main()
{
    FILE *in, *out;
    long int i, p1, p2, phi, nr, A, modulo;
    long int result, p;
	
    in = fopen("inversmodular.in", "r");
    out = fopen("inversmodular.out", "w");
    fscanf(in, "%ld %ld", &A, &modulo); 

    for(p1 = 1, p2 = 0, nr = modulo; nr % 2 == 0; nr /= 2)
        p2 = p1, 
        p1 *= 2;
    phi = p1 - p2;
    for(i = 3; nr != 1; i += 2)
    {
            for(p1 = 1, p2 = 0; nr % i == 0; nr /= i)
                p2 = p1,
                p1 *= i;
            phi *= (p1 - p2);
    }
    
    phi--;
    for(result = 1, p = A, i = 1; i <= phi; i <<= 1, p *= p, p %= modulo)
    	if(i & phi)
    		result *= p,
    		result %= modulo;
    
    fprintf(out, "%ld\n", result);
    
    fclose(in);
    fclose(out);
    return 0;
}