#include <iostream>
#include <fstream>

using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
long long recPow(long long n, long long int p)
{
    if (p < 0)
        return recPow(1 / n, -p);
    if (p == 0)
        return 1;
    if (p % 2 == 0)
        return recPow(n * n, p / 2);
    if (p % 2 == 1)
        return n * recPow(n * n, (p - 1) / 2);
}
long long phi(long long n)
{
    long long result = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}
int main()
{
    long long a,n;
    in>>a>>n;
    long long modulo=phi(n); //(a*x)%m == 1  (a*a^phi(m)-1)%m==1
    out<<recPow(a,modulo-1)%n;
    return 0;
}