#include<fstream>

using namespace std;

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

long long a, n;

long long ridicare_putere(long long x, long long y){

    long long r = 1;
    while(y){

        if(y%2)
            r = (r * x) % n;
        x = (x * x) % n;
        y /= 2;
    }
    return r;
}

long long descompunere(long long N){

    long long i , r = N, p;
    for(i = 2; i * i <= N; i++){
        p = 0;
        while(N % i == 0)
            N /= i, p++;
        if(p)
            r = r / i * (i - 1);

    }
    if(N>1)
        r = r / N * (N-1);
    return r;
}

void rezolvare(){

    f >> a >> n;
    g << ridicare_putere(a, descompunere(n) - 1);
}
int main(){

    rezolvare();
    return 0;
}