#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
unsigned long long k,m;
unsigned long long int lgput(unsigned long long int a,unsigned long long int b)
{
    if(b==0) return 1;
        if(b%2==0)
        {
            return lgput(a*a%m,b/2);
        }
        else
            return a*lgput(a*a%m,(b-1)/2)%m;
}


int descompunere()
{
    int p=0,i;
    if(k%2==1)
        p+=1;
    for(i=3;i<=k;i+=2)
        if(k%i!=0)
            p+=1;
    return p;
}

int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    int n,o;
    f>>n;
    f>>k;
    m=k;
 /*   k=9;
    g<<descompunere()<<" ";*/
    int i=2;
    if(k%2==0)
    {
        o=descompunere();
        g<<lgput(n,o-1);
    }
    else
    {
        i=3;
        int q;
        q=sqrt(k);
        while(i<=q)
        {
            if(k%i==0)
            {
                o=descompunere();
                g<<lgput(n,o-1);
                i=q+6;
            }
            i+=2;
        }
        if(i!=q+8)
            g<<lgput(n,k-2);
    }
   // g<<n<<" "<<k-2;
    f.close();
    g.close();
    return 0;
}