#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int phi(int x) {
    int d=2,cx=x,e;
    while(d*d<=x) {
        e=0;
        while(!(x % d)) {
            e=1;
            x/=d;
        }
        if(e==1) {
            cx/=d;
            cx*=(d-1);
        }
        d++;
    }
    if(x>1) {
        cx/=x;
        cx*=(x-1);
    }
    return cx;
}
int lgput(int x,int y,int n ) {
    int p = 1;
    while( y ) {
        if( y & 1 )
            p = (p * x) % n;
        x=(x*x)% n;
        y >>= 1;
    }
    return p;
}
int main() {
    int a,n,ph;
    fin>>a>>n;
    ph=phi(n);
    fout<<lgput(a,ph-1,n);
    return 0;
}