#include <bits/stdc++.h>
#define LL long long

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

LL n, m, p;

LL phi(LL nr)
{
    LL cur = nr;
    for(LL i = 2; i*i <= nr; ++i)
    {
        if(nr % i == 0){
            while(nr%i == 0) nr/=i;
            cur = (cur/i) * (i-1);
        }
    }
    if(nr != 1) cur = cur/nr * (nr-1);
    return cur;
}

int main()
{
    fin >> n >> m;
    LL sol = 1;
    p = phi(m)-1;
    for(LL i=1; i<=p; i<<=1)
    {
        if(i & p)sol = (sol*n) % m;
        n = (n*n)%m;
    }
    fout << sol;
    return 0;
}