#include <fstream>

using namespace std;
ifstream cin ("inversmodular.in");
ofstream cout ("inversmodular.out");
#define ll long long
ll mod;
ll ridput(ll b, ll e)
{
    ll r = 1;
    while (e)
    {
        if (e % 2)
            r = (r * b) % mod;
        b = (b * b) % mod;
        e /= 2;
    }
    return r;
}
ll phi(ll n)
{
    ll r = n, f = 2;
    while (f * f <= n && n != 1)
    {
        if (!(n % f))
        {
            r = r * (f - 1) / f;
            while (!(n % f))
                n /= f;
        }
        f++;
    }
    if (n != 1)
        r = r * (n - 1) / n;
    return r;
}
int main()
{
    ll a, b;
    cin >> a >> b;
    mod = b;
    cout << ridput(a, phi(b) - 1);
    return 0;
}