#include <bits/stdc++.h>
using namespace std;

long long n, p, k;

long long power(long long n, long long f) {
  	if (f == 0)
  		return 1;
	unsigned long long r = 1;
  	while(f > 1)
  	{
  		if (f % 2 == 1)
  			r = (1LL * r * n) % p;
  		n = (1LL * n * n) % p;
  		f = f / 2;
	}
	return (1LL * r * n) % p;
}

int main()
{
	ifstream cin("inversmodular.in");
	ofstream cout("inversmodular.out");
	cin >> n >> p;
	k = p;
	long long x = p;
	for (int i = 2; (x != 1); i++)
		while (x % i == 0)
		{
			k --;
			x /= i;
		}
	cout << power(n, k - 1);
}