#include <iostream>
#include <fstream>
#define ll long long

using namespace std;

#ifdef LOCAL
    ifstream f("a.in");
    ofstream g("a.out");
#else
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
#endif // LOCAL

ll logput(ll a, ll n, ll MOD)
{
    if (n == 0) return 1;
    ll temp = logput(a, n/2, MOD) % MOD;
    if (n%2 == 1) return (((1LL * temp * temp) % MOD) * a) % MOD;
    if (n%2 == 0) return (1LL * temp * temp) % MOD;
}

ll phi(ll x)
{
    ll ans = x;
	for (ll 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;
}

ll a, n;

int main()
{
    f >> a >> n;
    g << logput(a, phi(n)-1, n);

    f.close();
    g.close();
    return 0;
}