#include <cstdio>
#include <cmath>

using namespace std;

FILE * iFile;
FILE * oFile;

int n, p, a, rez;

void read()
{
	fscanf(iFile, "%d %d", &n, &p);
}

void solve()
{
	int i;
	
	rez = 1;
	a = 1;
	
	for(i=0;i<=31;i++)
		if((n >> i) & 1)
			rez = (rez * pow((double) n, (double)pow((double)2, (double)a)), a = a * n)%p; 
}

void write()
{
	fprintf(oFile, "%d", rez);	
}

int main()
{
	iFile = fopen("lgput.in", "r");
	oFile = fopen("lgput.out", "w");
	
	read();
	solve();
	write();
	
	fclose(iFile);
	fclose(oFile);
	
	return 0;
}