#include <stdio.h>
using namespace std;

#define MOD 1999999973

int bin[10001];
long long p, N, rez = 1;
int i, j;

int main ()
{
    FILE *f = fopen ("lgput.in","r");
    FILE *g = fopen ("lgput.out","w");
    fscanf (f, "%lld %lld", &N, &p);

    while (p)
    {
        i ++;
        bin[i] = p % 2;
        p /= 2;
    }

    for (j=i; j>=1; --j)
    {
        rez = (rez * rez) % MOD;
        if (bin[j])
            rez = (rez * N) % MOD;
    }

    fprintf (g, "%lld\n", rez);

    fclose (g);
    fclose (f);
    return 0;
}