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

typedef long long ll;

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

ll n, p, k = 1;

/*ll lgpower(ll n, ll h)
{
	ll sol = 1;
	
	for (int i = 0; (1 << i) <= h; ++i)
	{
		if (((1 << i) & h) > 0)
			sol = (sol * n) % p;
		n = (n * n) % p;
	}
	return sol;
}*/

ll lgpower(ll x, ll j){
    ll ans=1;
    while(j){
        if (j%2==1){
            ans=(ans*x)%p;
            j--;
        }
        j/=2;
        x=(x*x)%p;
    }
    return ans;
}

bool prim(ll r)
{
	for (int i = 2; i <= sqrt(r); i++)
		if (r % i == 0)
			return 0;
	if (r == 1 || r == 0)
		return 0;
	return 1;
}

int main()
{
	fin >> n >> p;
	ll x = p;
	ll i = 2;
	if (prim(p))
	{
		fout << lgpower(n, p - 2);
		return 0;
	}
	while (x != 1)
	{ 
		while (x % i == 0)
		{
			ll t = x;
			ll nr = 0;
			while (t % i == 0)
			{
				nr++;
				t /= i;
			}
			k *= lgpower(i, nr - 1) * (i - 1);
			k %= p;
			x /= i * nr;
		}
		i++;
	}
	fout << lgpower(n, k - 1);
	return (0);
}