#include <fstream>
using namespace std;
ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");
int const NM = 1e5;
typedef long long ll;
int nrp (int nr){
    int i = 2 , c = 0 , sol = nr;
    while (i * i <= nr){
        if (nr % i == 0){
            c = 0;
            while (nr % i == 0)
                nr /= i;
            sol = (sol / i) * (i - 1);
        }
        ++ i;
    }
    if (nr > 1)
        sol = sol / nr * (nr - 1);
    return sol;
}
int main()
{
    int a , n;
    f >> a >> n;
    int p = nrp (n) - 1 , best = 1 , x = a;
    for(int i = 0 ; (1 << i) <= p ; ++ i){
        if ((1 << i) & p)
            best = (best * x) % n;
        x = (x * x) % n;
    }
    g << best;
    return 0;
}