#include<stdio.h>
#define LL long long


LL N,M;

int main()
{
	freopen("invers.in","r",stdin);
	freopen("invers.out","w",stdout);
	scanf("%lld %lld\n",&N,&M);
	/*
	pornind de la X^P = X (% P),orice P -prim, Teorema lui ferma, se inmulteste cu X^(-1) si se obtine
	X^(P - 1) = 1 (%P)
	Se rescrie: 
	X * X^(P - 2) = 1 (%P), 1 fiind elementrul neutru al inmultirii reiese ca X^(P-2) e inversul modular al lui X
	ridicarea la putere se face in timp logaritmic
	*/
	LL nr = N;
	LL cur = 1;
	LL put = M - 2;
    for(LL p = 1;p <= put;p <<= 1)
    {
	 	if (p & put) cur = (cur * nr) % M;
	  	nr = (nr * nr) % M;
	}
	printf("%lld\n",cur);
	return 0;
}