#include <cstdio>

FILE *in = fopen("inversmodular.in","r"), *out = fopen("inversmodular.out","w");

int phi(int nr)
{
    long long answ = nr;

    int x = nr;
    for ( int i = 2; i*i <= x; ++i )
        if ( nr % i == 0 )
        {
            answ = answ * (i - 1);
            answ /= i;

            while ( nr % i == 0 )
                nr /= i;
        }

    if ( nr > 1 )
    {
        answ = answ * (nr - 1);
        answ /= nr;
    }

    return (int)answ;
}

int pow(int base, int exp, int mod)
{
    if ( exp == 1 )
        return base;

    long long t = pow(base, exp >> 1, mod) % mod;

    t *= t;
    t %= mod;

    if ( (exp & 1) )
        t *= base;

    return t % mod;
}

int main()
{
    int a, b;

    fscanf(in, "%d %d", &a, &b);

    fprintf(out, "%d\n", pow(a, phi(b)-1, b));

    return 0;
}