#include <iostream>
#include <fstream>

#define dataType unsigned long long
#define mod 1999999973

using namespace std;

dataType n, p;

dataType lgput(dataType n, dataType p)
{
    
    if (p == 1)
        return n;
    
    dataType half = lgput(n, p/2) % mod;
    
    if (p % 2 == 0)
        return (half * half) % mod;
    else
        return (((half * half) % mod) * n) % mod;
    
}


int main()
{
    
    ifstream fi("lgput.in");
    ofstream fo("lgput.out");
    
    fi >> n >> p;
    
    fo << lgput(n, p) << "\n";
    
    fi.close();
    fo.close();
    
    return 0;
}