#include <fstream>
#include <cmath>
#define int long long int

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
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(int x,int n){
    int q;
    if(n==0)
        return 1;
    if(n%2==0){
        return x*exp(x,n/2);
    }
    else{
        q = n/2;
        return x*exp(x,q)*exp(x,q);
    }
}
signed main()
{
    int a,b,n;
    //cin>>a>>b;
    //cout<<exp(a,b);
    cin>>a>>n;
    cout<<exp(a,Phi(n)-1)%n;
    return 0;
}