#include <stdio.h>

typedef unsigned long long u64;
//ridicare la putere in timp logaritmic
//il ridic pe x la y si fac totul modulo z

u64 pow_x(u64 x, u64 y, u64 z)
{
    u64 rezultat = 1;
    u64 dynamic = x;

    while(y){
        if(y & 1){
            rezultat *= dynamic;
            rezultat %= z;
        }
        dynamic *= dynamic;
        dynamic %= z;
        y >>= 1;
    }
    return rezultat;
}

int main(void)
{
    u64 x, y, z;
    FILE *f = fopen("lgput.in", "r");
    fscanf(f, "%lld%lld", &x, &y, 1999999973);
    FILE *g = fopen("lgput.out", "w");
    fprintf(g, "%lld", pow_x(x, y, 1999999973));
    fclose(f);
    fclose(g);
}