#include <fstream>
#include <vector>
std::ifstream cin("inversmodular.in");
std::ofstream cout("inversmodular.out");
#define LL long long int

LL A,N;
LL getPHI(LL n){
    LL prime=n;
    for(LL i=2;i*i<=n;i++)
        if(n%i==0){
            while(n%i==0)n/=i;
            prime=(prime/i)*(i-1);//dupa formula lui euler(Euler's totient function)
    }
    if(n!=1)prime=(prime/n)*(n-1);//pt n prim! sau sanse sa fi ramas ceva,
    return prime;                   //un multiplu neverificat??idk
}

int main()
{
    cin>>A>>N;
    LL put=getPHI(N)-1,sol=1;

    for(LL i=1;i<=put; i<<=1){
        if((i&put)>0){
            sol=(sol*A)%N;
        }
        A=(A*A)%N;
    }
    cout<<sol%N;
}