#include <fstream>
#define NRM 1999999973
using namespace std;
ifstream f("lgput.in");
ofstream g("lgput.out");

long long n,p,P=1;

int main()
{
    int i,j;
    f>>n>>p;
    P=n;
    for(i=2;p>1;i++){
        while(!(p%i)){
            for(j=1;j<i;j++)
                P=(P*n)%NRM;
            p/=i;
            n=P;}}
    g<<P;
    f.close();
    g.close();
    return 0;
}