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

using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

LL a, n, x;

int gcd(int a, int b)
{
	if(b == 0) return a;
	else return gcd(b, a % b);
}

LL lgput(int num, int put)
{
	LL rs = 1, k = num;
	while(put != 0)
	{
		if(put % 2 == 1) rs = (rs * k) % n;
	 	k = (k * k) % n;
	 	put /= 2;
	}
	return rs % n;
}

LL fidin(LL num)
{
	LL res = 0;
	for(int i = 1; i < num; i++)
	{
		if(gcd(num, i) == 1) res++; 
	}
	return res-1;
}

int main(){
	in >> a >> n;
	out << lgput(a, fidin(n));
	cout << lgput(5, 5) << '\n';
	cout << fidin(n);
	return 0;
}