#include <fstream>

using namespace std;

void read();
void solve();
long long int phi(long long int n);
long long int pow(long long int x, long long int n, long long int MOD);

long long int N,A;

int main()
{
	read();
	solve();
	return 0;
}

void read()
{
	ifstream fin("inversmodular.in");
	fin>>A>>N;
}

void solve()
{
	ofstream fout("inversmodular.out");
	long long int tn = phi(N);
	fout<<pow(A,tn-1,N);
}

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

long long int pow(long long int x, long long int n, long long int MOD)
{
	long long int result = 1;
	while(n>0)
	{
		if(n % 2 == 0)
		{
			x = (x * x) % MOD;
			n = n / 2;
		}
		else
		{
			result = (result * x) % MOD;
			n--;
		}
	}
	return result;
}