#include <fstream>

using namespace std;

int put(int n, int p, int m)
{
    int a = 1;
    while (p != 0)
    {
        if (p % 2 == 1)
        {
            a *= (long long)n;
            a %= m;
        }
        n *= (long long)n;
        n %= m;
        p /= 2;
    }
    return a;
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int phi = 1;
    int d = 2;
    int n, a;
    fin >> a >> n;
    int cn = n;
    phi = n;
    while (d * d <= n)
    {
        int p = 0;
        while (n % d == 0)
        {
            p++;
            n /= d;
        }
        if (p > 0)
        {
            //phi *= put(d, p - 1);
            phi /= d;
            phi *= (d - 1);
        }
        d++;
    }
    if (n != 1)
    {
        phi /= n;
        phi *= (n - 1);
    }
    long long inv = put(a, phi - 1, cn);
    fout << inv;
    return 0;
}