#include <iostream>
#include <fstream>
#define LL long long int
using namespace std;

LL N,A;

LL phi(LL nr){
    LL i,res=nr;
    for (i=2; i*i<=nr; i++)
        if (nr%i==0){
            while (nr%i==0)
                nr/=i;
            res=res/i*(i-1);
        }
    if (nr>1) res=res/nr*(nr-1);

    return res;
}

int main(){
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    in >> A >> N;

    LL i,p=phi(N)-1,res=1;
    for (i=1; i<=p; i<<=1){
        if (p&i)
            res=(res*A)%N;
        A=(A*A)%N;
    }

    out << res;
    return 0;
}