#include <stdio.h>

#define IN "lgput.in"
#define OUT "lgput.out"

static const unsigned long mod = 1999999973;
static unsigned long n;

static unsigned long lgput(unsigned long p)
{
    if (p == 0)
        return 1;
    if (p == 1)
        return n;

    return lgput(p >> 1) % mod * lgput(p >> 1) % mod;
}

int main(void)
{
    unsigned long p;

    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);

    scanf("%lu %lu", &n, &p);
    printf("%lu\n", lgput(p) % mod);

    return 0;
}