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

#define NR 1999999973

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

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);
    }

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

    int res = lgput(n, p)%NR;
    fprintf(out, "%d\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;
}