#include <bits/stdc++.h>
#define LL long long

using namespace std;

LL N,M;

LL phi(LL n) {
    LL result = n;

    for (LL p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0)
                n /= p;
            result *= (1.0 - (1.0 / (float)p));
        }
    }
    if (n > 1)
        result *= (1.0 - (1.0 / (float)n));

    return result;
}

int main(){

	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);

	scanf("%lld %lld\n",&N,&M);

    LL put = phi(M) - 1; // 7
	LL nr = N; // 3
	LL crt = 1;

    for(LL p = 1; p <= put; p <<= 1){
	 	if (p & put)
            crt = (crt * nr) % M; // 3 11
	  	nr = (nr * nr) % M; // 9 1
	}

	printf("%lld",crt);

	return 0;
}