#include <fstream>
#include <vector>
#define NMAX 45000
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long ciur[NMAX],i,A,N,n,rez,ok;
vector <int> prim;
void ciur2()
{
    prim.push_back(2);
    for(int i=3; i<=NMAX; i += 2)
    {
        if(ciur[i]==0)
        {
            prim.push_back(i);
            for(int j=i*3; j<=NMAX; j += i<<1)
                ciur[j]=1;
        }
    }
}
void putere()
{
    unsigned long long putere2=1;
    while(rez>0)
    {
        if(rez%2==1)
        {
            putere2 = putere2 * A % N;
            rez--;
        }
        A = A * A % N;
        rez >>=1;
    }
    g<<putere2;
}
int main()
{
    f>>A>>N;
    ciur2();
    A %= N;
    n=rez=N;
    for(i=0; i<prim.size() && n>=prim[i]; ++i)
    {
        if(n%prim[i]==0)
        {
            while(n%prim[i]==0)
                n=n/prim[i];
            rez=rez/prim[i]*(prim[i]-1);
        }
    }
    if(n!=1)
        rez=rez/n*(n-1);
    rez=rez-1;
    putere();
    return 0;
}