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

#define MOD 1999999973

uint64_t putere(uint64_t n, uint64_t p, uint64_t m) {
    uint64_t rez = 1;
    n %= m;

    while (p > 0) {

        if (p & 1) { //verificam imparitatea
            rez = (rez * n) % m;
        }
        n = (n * n) % mod;
        p >>= 1; //impartim puterea la 2
    }

    return rez;
}

int main()
{
    FILE *f1=fopen("lgput.in", "r"),*f2=fopen("lgput.out","w");

    if(f1==NULL||f2==NULL)
    {
        printf("eroare");
        return 1;
    }

    uint64_t N, P;
    fscanf(f1, "%llu %llu", &N, &P);

    uint64_t rez= putere(N, P, MOD);
    fprintf(f2, "%llu\n", rez);

    fclose(f1);
    fclose(f2);

    return 0;
}