#include <stdio.h>
#include <stdlib.h>

#define NR 1999999973

long long lgput(long long n, long long p)
{
    if(p == 0)
        return 1;
    else if(p%2 == 0)
        return lgput(n*n%NR, p/2);
    else
        return n*lgput(n*n%NR, p/2)%NR;
}

int main(void)
{

    FILE *in, *out;

    if((in = fopen("lgput.in", "r")) == NULL)
    {
        perror("Eroare la deschiderea fisierului de intrare");
        exit(EXIT_FAILURE);
    }

    if((out = fopen("lgput.out", "w")) == NULL)
    {
        perror("Eroare la deschiderea fisierului de iesire");
        exit(EXIT_FAILURE);
    }

    long long n, p;
    if(fscanf(in, "%lld %lld", &n, &p) != 2)
    {
        perror("Eroare la citirea datelor din fisierul de intrare");
        exit(EXIT_FAILURE);
    }

    long long res = lgput(n, p);
    fprintf(out, "%lld\n", res);

    if(fclose(in) != 0)
    {
        perror("Eroare la inchiderea fisierului de intrare");
        exit(EXIT_FAILURE);
    }

    if(fclose(out) != 0)
    {
        perror("Eroare la inchiderea fisierului de iesire");
        exit(EXIT_FAILURE);
    }

    return 0;
}