#include <cstdio>

using namespace std;

inline long long bin (long long a, long long nr, long long n)
{
    if (nr == 1) return a;

    long long x = bin (a, nr / 2, n);
    x *= x;
    x %= n;

    if (nr & 1)
    {
        x *= a;
        x %= n;
        return x;
    }

    return x;
}

int main ()
{
    freopen ("inversmodular.in", "r", stdin);
    freopen ("inversmodular.out", "w", stdout);

    long long a, n;
    scanf ("%lld %lld", &a, &n);

    long long nr = 1, cn = n;
    for (int i = 2; i * i <= n; ++i)
    {
        int nrr = 1;
        while (!(n % i))
        {
            n /= i;
            ++nrr;
        }

        nr *= 1LL * nrr;
    }

    if (n > 1) nr *= 2LL;
    nr = cn - nr;

    a = bin (a, nr, n);

    printf ("%lld\n", a);

    return 0;
}