#include <iostream>
#include <fstream>
#define MOD 1999999973

using namespace std;

typedef long long ll;

ll n,p;
ll rest(ll nr, ll put){
    if(put==1){
        return nr%MOD;
    } else {
        if(put%2==0){
            ll r=rest(nr,put/2);
            return r*r%MOD;
        } else {
            ll r=rest(nr,put-1);
            return r*nr%MOD;
        }
    }
}

int main()
{
    ifstream f ("lgput.in");
    ofstream g ("lgput.out");
    f>>n>>p;
    g<<rest(n,p);
    f.close ();
    g.close ();
    return 0;
}