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

long long getphi(long long N) {
	long long result = N;
	long long i;
	for (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);

    long long A, N;

    scanf("%lld %lld", &A, &N);
    long long phi = getphi(N) - 1;

    long long it = A, result = 1;
    long long i;

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

    printf("%lld", result);

    return 0;
}