#include <fstream>
#include <vector>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
vector <int> prim;
int baza,n,ind,d,phi;
int exp(int a, int x)
{
    if (x==0) return 1;
    if (x%2==1) return ((a%n)*(exp(a,x-1)%n))%n;
    int put=exp(a,x/2)%n;
    return ((put%n)*(put%n))%n;
}
char ciur[45005];
int main()
{cin>>baza>>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=0; 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<<exp(baza,phi-1)%n;
    return 0;
}