#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long A,N,ans,pow;

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 main(){

    fin >> A >> N;

    pow = getphi(N)-1;

    A%=N;

    ans = 1;

    while(pow){
        if(pow&1)
            ans=(ans*A)%N;
        A=(A*A)%N;
        pow/=2;
    }

    fout << ans << "\n";

}