#include <cstdio>

int A, B;

int phi(int x)
{
    int rnow = x, aux = x;
    for (int i = 2; i * i <= aux; ++i)
        if (aux % i == 0)
        {
            rnow = rnow / i * (i - 1);
            while (aux % i == 0)
                aux /= i;
        }
    if (aux != 1) rnow = rnow / aux * (aux - 1);

    return rnow;
}
int power(int x, int y)
{
    if (y == 0) return 1;
    if (y & 1) return 1LL * x * power(x, y - 1) % B;
    return power(1LL * x * x % B, y / 2);
}

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

    scanf("%d %d", &A, &B);
    printf("%d\n", power(A, phi(B) - 1));
}