#include <fstream>
#include <cmath>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
long long int a,b,mod;
int Phi(int n){
    int f = 1;
    int d,p,m,i;
    int alf;
    for(d=2;d*d<=n;d++){
        if(n%d==0){
            while(n%d==0){
                f*=d;
                n/=d;
            }
            f/=d;
            f*=(d-1);
        }
    }
    if(n>1){
        f*=(n-1);
    }
    return f;
}
int exp(long long int x,long long int n){
    long long int q;
    if(n==0)
        return 1;
    if(n%2==1){
        return x*exp(x,n-1)%mod;
    }
    q = exp(x,n/2);
    return (q*q)%mod;
}
int main()
{
    //cin>>a>>b;
    //cout<<exp(a,b);
    cin>>a>>mod;
    cout<<exp(a,Phi(mod)-1);
    return 0;
}