#include <fstream>

using namespace std;

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

int main(){
    int a,n;
    fin>>a>>n;
    int p=1,d;
    for(d=2;d<n*n;d++){
        if(n%d==0){
            p=p*d;
            p=p*(n/d);
        }
    }
    if(d*d==n){
        p=p*d;
    }
    int x=1,a2=a;
    for(int i=1;i<=p-1;i*=2){
        if((i&a)!=0){
            x=x*a2%n;
        }
        a2=a2*a2%n;
    }
    fout<<x<<"\n";
    return 0;
}