#include <iostream>
#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int x, c;
long long a[100];
int main()
{
f>>x>>c;
int p=1,i,aux;
int auxx=x;
for (i=2;i*i<=auxx;i++)
{
    aux=1;
    while (x%i==0)
    {
        aux++;
        x/=i;
    }
    p*=aux;
}
p=auxx-p-1;
a[0]=1;
a[1]=auxx;
i=1;
for (i=2;i<=32;i++)
{
    a[i]=a[i-1]*a[i-1];
    a[i]%=c;
}
i=0;
long long sol=1;
while (auxx)
{
    i++;
    if (auxx%2==1) {sol*=a[i];sol%=c;}
    auxx/=2;
}
g<<sol;

    return 0;
}