#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int a,n,p,i,l,c;
long long pow,ans;
int main()
{
    f>>a>>n;
    l=n;
    p=1;
    for (i=2;i*i<=n;i++)
    if (n%i==0){
    n/=i;
    p*=(i-1);
    while(n%i==0)
      n/=i,p*=i;
    }
    if (n>1)
       p*=(n-1),n=1;
    p--;
    ans=1;
    pow=a%l;
    for (i=0;(1<<i)<=p;i++)
    {
       if (p & (1<<i))
         ans=((ans%l)*(pow%l))%l;
       pow=((pow%l)*(pow%l))%l;
    }
    g<<ans<<' ';
    return 0;
}