#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
bool isp(long long a)
{
    if(a<2)
        return 0;
    for(long long i=2;i*i<=a;i++)
        if(a%i==0)
            return 0;
    return 1;
}
long long lg(long long prim,long long a)
{
    long long sol=0;
    while(a%prim==0)
    {
        sol++;
        a/=prim;
    }
    return sol;
}
long long expow(long long a,long long b,long long mod)
{
    long long sol=1;
    for(int i=0;(1LL<<i)<=b;i++)
    {
        if(b&(1LL<<i))
            sol=sol*a%mod;
        a=a*a%mod;
    }
    return sol;
}
int main()
{
    long long a,n,p=1;
    cin>>a>>n;
    for(long long i=1;i*i<=n;i++)
        if(n%i==0)
        {
            if(isp(i))
                p*=(i-1)*expow(i,lg(i,n)-1,2000000009);
            if(i*i==n)
                break;
            if(isp(n/i))
                p*=(n/i-1)*expow(n/i,lg(n/i,n)-1,2000000009);
        }
    cout<<expow(a,p-1,n);
    return 0;
}