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


LL N,M;

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.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
	Se utilizeaza cand se fac impartiri modulo un numar prim, de exemplu cand avem de calculat combinari de x luate cate y, in loc 
	sa facem (x!) / (y! * (x - y)!), fiindca modulo un numar prim nu este definita inmultirea , vom face :
	(x!) * invers(y!) * invers( (x -y)! ), si astfel se scapa de impartire.
	*/
	LL nr = N;
	LL cur = 1;
	LL put = M - 2;
    for(LL p = 1;p <= put;p <<= 1)
    {
	 	if (p & put) cur = ((long long)cur * nr) % M;
	  	nr = ((long long)nr * nr) % M;
	}

	printf("%lld\n",cur);
	return 0;
}