#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int A,N,ok;
int getphi(int n){
    int ans=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            while(n%i==0)
                n/=i;
            ans-=ans/i;
        }
    }
    if(n!=1)
        ans-=ans/n;
    return ans;
}
long long exp(long long b,long long p)
{
    unsigned long long ans=1;
    b=b%N;
    while(p)
    {
        if(p%2==1)
            ans=(ans*b)%N;
        b=(b*b)%N;
        p=p/2;
    }
    return ans;
}
int main(){
    fin>>A>>N;
    int x=getphi(N);
    fout<<exp(A,x-1);
    fin.close();fout.close();
    return 0;
}