#include <bits/stdc++.h>

using namespace std;

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

long long n,m,poww,mask,rez;

long long phi (long long m)
{
    long long rez=m;
    for (long long i=2; i*i<=m; i++)
        if (m%i==0)
        {
            while (m%i==0)  m/=i;
            rez = (rez/i) * (i-1);
        }
    if (m!=1)   rez = rez / m * (m-1);
    return rez;
}


int main()
{
    fin>>n>>m;
    poww=phi(m)-1;
    rez=1;
    for (mask=1; mask<=poww; mask<<=1)
    {
        if (mask&poww)
            rez = (rez*n)   % m;
        n = (n*n) % m;
    }
    fout<<rez;
    return 0;
}