#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 i=3,p=0;
    if(k%2==0)
    {
        p+=1;
        k/=2;
        while(k%2==0)
            k/=2;
    }
    while(k>1)
    {
        if(k%i==0)
        {
            p+=1;
            k/=i;
            while(k%i==0)
                k/=i;
        }
        i+=2;
    }
    return p;
}

int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    int n,o;
    f>>n;
    f>>k;
    m=k;
    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;
}