#include <fstream>
#include <iostream>
using namespace std;


long long n,m;


long long phi(long long nr)
{
    long long a = nr;
    for(long long i = 2; i * i <= nr; ++i){
        if(nr % i == 0){
            while(nr % i == 0)
                nr /= i;
            a = (a / i) * (i - 1);
        }
    }
    if(nr != 1)
        a = (a / nr) * (nr - 1);
    return a;
}
int main(){
    ifstream fin ("inversmodular.in");
    ofstream fout ("inversmodular.out");

    long long put,p,congr=1,nr;

    fin >> n >> m;

    put = phi(m) - 1;

    nr = n;
    for( p = 1; p <= put; p <<= 1){
        if(p & put)
            congr = (congr * nr) % m;
        nr = (nr * nr) % m;
    }

    fout << congr;

    return 0;
}