#include <fstream>
using namespace std;
using ll = long long;

const string name("inversmodular");
ifstream fin(name + ".in");
ofstream fout(name + ".out");

ll Phi(ll nr){
    ll d = 2, rez = nr;
    while(nr > 1){
        if(nr % d == 0){
            rez = rez / d;
            rez = rez * (d - 1);
            while(nr % d == 0)
                nr /= d;
        }
        ++d;
        if(d * d > nr)
            d = nr;
    }
    return rez;
}

ll putere(ll a, ll pow){
    if(!pow)
        return 1;
    if(pow % 2)
        return putere(a, pow / 2) * putere(a, pow / 2) * a;
    return putere(a, pow / 2) * putere(a, pow / 2);
}

int main(){

    ll a, n;
    fin >> a >> n;
    ll put = Phi(n);
    fout << putere(a, put - 1) % n;

    return 0;
}