#include <bits/stdc++.h>

using namespace std;

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

#define int long long

int b;

int lgput(int a, int n)
{
	int ans = 1;
	while(n > 0)
	{
		if(n & 1)
		{
			ans *= a;
			ans %= b;
			n--;
		}
		a = a * a;
		a %= b;
		n >>= 1;
	}
	return ans;
}

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

main()
{
	int a;
	fin >> a >> b;
	int power = phi(b) - 1;
	fout << lgput(a, power);
}