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

#define MOD 1999999973

// Funcție pentru a calcula restul lui base^exp % MOD
uint64_t modular_pow(uint64_t base, uint64_t 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 *input_file = fopen("lgput.in", "r");
    FILE *output_file = fopen("lgput.out", "w");

    if (input_file == NULL || output_file == NULL) {
        printf("Eroare la deschiderea fișierelor.\n");
        return 1;
    }

    uint64_t N, P;
    // Citim valorile N și P din fișierul de intrare
    fscanf(input_file, "%llu %llu", &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(output_file, "%llu\n", result);

    // Închidem fișierele
    fclose(input_file);
    fclose(output_file);

    return 0;
}