#include <fstream>
#include <cmath>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int ca , i=2 , a , n , v[20] , s=0 ;

int main()
{
    in>>a>>n;
    ca=a;
    while (ca!=1)
    {
        if (ca%i==0)
        {
            ca/=i;
            v[i]++;
        }
        else i++;
    }
    for (int i=2 ; i<n ; i++ )
    {
     if (v[i])
        s=s+v[i]* pow(i , v[i]);
    }
    a=pow(a , s);
    a=a %n;
    out<<a;
    return 0;
}