#include <fstream>
#include <vector>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
vector <int> prim;
int baza,n,ind,d,phi,ret;
int exp(int a, int x)
{
    if (x==0) return 1;
    if (x%2==1) return ((a%ret)*(exp(a,x-1)%ret))%ret;
    int put=exp(a,x/2)%ret;
    return ((put%ret)*(put%ret))%ret;
}
char ciur[45005];
int main()
{cin>>baza>>n; ret=n;
ciur[0]=1; ciur[1]=1;
for (int i=2; i*i<=45000; i++)
{
    if (ciur[i]==0)
    {
        for (int j=i*i; j<=45000; j+=i)
            ciur[j]=1;
    }
}
for (int i=2; i<=45000; i++)
    if (ciur[i]==0) {prim.push_back(i);}
d=prim[ind]; phi=n;
while (d*d<=n)
{
    if (n%d==0)
    {
        while (n%d==0) n/=d;
        phi=phi/d*(d-1);
    }
    ind++; d=prim[ind];
}
if (n>1) phi=phi/n*(n-1);
//cout<<phi<<'\n';
cout<<exp(baza,phi-1);
    return 0;
}