#include <stdio.h>
#include <stdint.h>

#define M (int64_t)1999999973

long long exp_log(int64_t x, int64_t n)
{

    if (n == 0)
        return 1;

    long long p = 1;
    while (n > 0)
    {
        p *= p;
        if (n % 2)
        {
            p *= x;
        }
        n = n / 2;
    }
    return p;
}

int main()
{
    FILE *file = fopen("lgput.in", "rb");
    FILE *fileout = fopen("lgput.out", "w");
    int64_t n, p;
    fscanf(file, "%ld", &n);
    fscanf(file, "%ld", &p);

    fclose(file);

    fprintf(fileout, "%lld", exp_log(n, p) % M);
    fclose(fileout);
    return 0;
}