#include <stdio.h>

FILE *F = fopen("lgput.in", "r");
FILE *G = fopen("lgput.out", "w");

unsigned int n, p;
long long sol = 1, a;

void Citire()
{
    fscanf(F, "%d %d", &n, &p);
    fclose(F);
}

void Calc_Put()
{
    unsigned int i;
    a = n;
    for (i = 0; (1 << i) <= p; ++i)
    {
        if (((1 << i) & p) > 0)
            sol = (sol * a) % 1999999973;
        a = (a * a) % 1999999973;
    }
}

void Afisare()
{
    fprintf(G, "%lld\n", sol);
    fclose(G);
}

int main()
{
    Citire();
    Calc_Put();
    Afisare();
    return 0;
}