/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on November 21, 2009, 7:53 PM
 */
#include <fstream>
#define Modulo 1999999973
/*
 *
 */
using namespace std;
ifstream in("lgput.in");
ofstream out("lgput.out");
int main()
{long long n, p, pow=1;
    in>>n>>p;
    if( 0 == n )
    {
        out<<'0';
        return 0;
    }
    if( 1 == n || 0 == p )
    {
        out<<'1';
        return 0;
    }
    if( 1 == p )
    {
        out<<n;
        return 0;
    }
    if( !(n&(n-1)) )
    {
        out<<(1<<p)%Modulo;
        return 0;
    }
    do
    {
        if( p&1 )
        {
            pow=(n*pow)%Modulo;
            --p;
        }
        n=(n*n)%Modulo;
        p>>=1;
    }while(p);
    out<<pow;
    return 0;
}