#include <stdio.h>

#define MOD 1999999973

long long exp_log_rec(long long x, long long n)
{
    if (n == 0)
        return 1;

    if (n % 2 == 0)
        return exp_log_rec((x * x) % MOD, n / 2) % MOD;

    if (n % 2 == 1)
        return (x * exp_log_rec((x * x) % MOD, n / 2)) % MOD;
}

int main(void)
{
    long long p, n;

    FILE *fr = fopen("lgput.in", "r");
    FILE *fw = fopen("lgput.out", "w");

    fscanf(fr, "%lld %lld", &n, &p);

    fprintf(fw, "%lld", exp_log_rec(n % MOD, p));

    fclose(fr);
    fclose(fw);

    return 0;
}