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