#include <stdio.h>

#define MOD 1999999973

long long lgput(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;

    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }

    return result;
}

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

    unsigned long long n, p;
    fscanf(input, "%llu %llu", &n, &p);

    unsigned long long result = lgput(n, p, MOD);
    fprintf(output, "%llu\n", result);

    fclose(input);
    fclose(output);
}