#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;
}
int exp(int a,int p){
    if(p==1)
        return a%N;
    if(p%2==0)
        return exp((a*a)%N,p/2)%N;
    return (a*exp((a*a)%N,p/2))%N;
}
int main(){
    fin>>A>>N;
    int x=getphi(N);
    fout<<exp(A,x-1);
    fin.close();fout.close();
    return 0;
}