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

using namespace std;

LL N,M;

LL getphi(LL nr){
	LL cur = nr;

	for(LL i = 2; i * i <= nr; ++i){
		if (nr % i == 0){
			while(nr % i == 0)
                nr /= i;
			cur = (cur / i) * (i - 1);
		}
	}

    if (nr != 1)
        cur = cur / nr * (nr - 1);

	return cur;
}

int main(){

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

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

    LL put = getphi(M) - 1;
	LL nr = N;
	LL crt = 1;

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

	printf("%lld\n",crt);

	return 0;
}