#include<stdio.h>
using namespace std;
long long aflaPhi(long long n)
{
    long long nr = n, i;
    for (i = 2; i * i <= n; i++)
    {
        if (nr % i == 0)
        {
            while (n % i == 0)
                n /= i;
            nr = (nr / i) * (i - 1);
        }
    }
    if (n != 1)
        nr = (nr / n) * (n - 1);
    return nr;
}
int main ()
{
    FILE *in, *out;
    in = fopen ("inversmodular.in", "r");
    out = fopen ("inversmodular.out", "w");
    long long x;
    long long n;
    fscanf (in, "%lld%lld", &x, &n);
    int put = aflaPhi(n) - 1;
    long long aux = x, invers = x, aux2 = 1;
    while (put > 1)
    {
        if (put % 2 == 0)
        {
            aux *= aux;
            put >>= 1;
            aux %= n;
        }
        else
        {
            aux2 *= aux;
            put--;
            aux2 %= n;
        }
    }
    invers = aux * aux2;
    fprintf (out, "%lld", invers % n);
    return 0;
}