#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int fi(int n){
    int f=n,d=2;
    while(d*d<=n){
        if(n%d==0){
            f/=d;
            f*=(d-1);
            while(n%d==0)
                n/=d;
        }
        d++;
    }
    if(n!=1){
        f/=n;
        f*=(n-1);
    }
    return f;
}

int putere(int a, int n, int mod){
    int p=1,cif;
    while(n!=0){
        cif=n%2;
        if(cif)
            p=(long long)p*a%mod;
        a=(long long)a*a%mod;
        n/=2;
    }
    return p;
}

int main(){
    int a,n,f;
    fin >>a>>n;
    f=fi(n);
    fout << putere(a, f-1, n);
    return 0;
}