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

#define MOD 1999999973

// Funcție pentru a calcula restul lui base^exp % MOD
uint64_t modular_pow(int base, int exp, uint64_t mod) {
    uint64_t result = 1;
    base %= mod;

    while (exp > 0) {
        // Dacă exp este impar, înmulțim result cu base și luăm restul împărțirii cu mod
        if (exp & 1) {
            result = (result * base) % mod;
        }
        // Înmulțim base cu el însuși și luăm restul împărțirii cu mod
        base = (base * base) % mod;
        // Reducem exp la jumătate
        exp >>= 1;
    }

    return result;
}

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

    if(f1==NULL||f2==NULL)
    {
        perror(NULL);
        return 1;
    }

    int N, P;
    fscanf(f1, "%d %d", &N, &P);

    // Calculăm restul lui N^P % MOD utilizând algoritmul de exponențiere rapidă
    uint64_t result = modular_pow(N, P, MOD);

    // Scriem rezultatul în fișierul de ieșire
    fprintf(f2, "%llu\n", result);

    // Închidem fișierele
    fclose(f1);
    fclose(f2);

    return 0;
}