#include <fstream>
using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

int putere(int bz, int exp, int mod)
{
    int rez = 1;
    while (exp != 0)
    {
        if (exp % 2 == 0)
        {
            bz *= bz;
            bz %= mod;
            exp /= 2;
        }
        else
        {
            rez *= bz;
            rez %= mod;
            --exp;
        }
    }
    return rez;
}

inline int Phi(int n)
{
    int sol = n;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0)
        {
            //do mod /= i;
            //while (mod % i == 0);
            while (n % i == 0)
                n /= i;
            sol = sol / i * (i - 1);
        }

    if (n != 1)
        sol = sol / n * (n - 1);

    return sol;
}

bool firicel(int nr)
{
    if (nr == 1) return false;
    if (nr % 2 == 0 && nr != 2) return false;
    for (int d = 3;d * d <= nr;d += 2)
        if (nr % d == 0)  return false;
    return true;
}

int main()
{
    int a, n;
    in>>a>>n;

    if (firicel(n))
    {
        out<<putere(a,n - 2,n);
    }
    else{
    int put = Phi(n) - 1;
    out << putere(a,put,n);}
}