/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 15, 2010, 2:58 PM
 */
#include <cstdio>
#define Modulo 1999999973

/*
 *
 */
using namespace std;
int main()
{
    unsigned long long n, p, rez=1, at_2;
    fscanf( fopen("lgput.in", "rt"), "%llu%llu", &n, &p );
    at_2=( (n%Modulo)*(n%Modulo) )%Modulo;
    while( p > 1 )
    {
        if( p&1 ) //if p is odd
        {
            rez=( (rez%Modulo)*(n%Modulo) )%Modulo;
            --p;
        }
        rez=( (rez%Modulo)*at_2 )%Modulo;
        p>>=1;
    }
    fprintf( fopen("lgput.out", "wt" ), "%llu", rez );
    return 0;
}