/* 
 * File:   pow.cpp
 * Author: alex
 *
 * Created on July 4, 2012, 1:32 PM
 */

#include <cstdlib>
#include <stdio.h>
#define D 1999999973
using namespace std;

long power(long N,long P)
{
    if(P == 0)
        return 1;
    if(P % 2 == 0)
        return power(N, P/2)*power(N, P/2);
    else
        return N * power(N, P/2)*power(N, P/2);
}
int main(int argc, char** argv) 
{
    FILE *f, *o;
    f = fopen("lgput.in", "r");
    o = fopen("lgput.out", "w");
    long N, P;
    fscanf(f, "%ld %ld", &N, &P);
    fprintf(o, "%ld\n", power(N, P)%D);
    return 0;
}