#include <bits/stdc++.h>

using namespace std;

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

int phi(int x)
{
	int ans = x;
	
	for(int i = 2; i * i <= x; ++i)
		if(x % i == 0)
		{
			while(x % i == 0)
				x /= i;
			
			ans = ans / i * (i - 1);
		}
	
	if(x > 1)
		ans = ans / x * (x - 1);
	
	return ans;
}

main()
{
	int x, y;
	fin >> x >> y;
	
	int p = phi(y) - 1;
	int ans = 1;
	
	for(; p; p >>= 1, x = (x * 1LL * x) % y)
		if(p & 1)
			ans = (ans * 1LL * x) % y;
	
	fout << ans << '\n';
}