#include <stdio.h>
#include <string.h>
#include <stdlib.h>

unsigned int getphi(unsigned int N) {
	unsigned int result = N;
	for (unsigned int i = 2; i * i <= N; i++) {
		if (N % i == 0) {
			while (N % i == 0) N /= i;
			result -= result / i;
		}
	}
	if (N != 1)
		result -= result / N;
	return result;
}

int main(int argc, char **argv) {
    freopen("inversmodular.in", "r", stdin);
    //freopen("inversmodular.out", "w", stdout);

    unsigned int A, N;

    scanf("%d %d", &A, &N);
    unsigned int phi = getphi(N) - 1;

    unsigned int it = A, result = 1;

    for (unsigned int i = 1; i <= phi ; i = i << 1) {
    	if (phi & i) {
    		result = (result * it) % N;
    	}
    	it = (it * it) % N;
    }

    printf("%u", result);

    return 0;
}