#include <fstream>

using namespace std;

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

typedef long long int64;

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