// http://infoarena.ro/problema/lgput
#include <fstream>
using namespace std;

#define modulo 1999999973

ifstream in("lgput.in");
ofstream out("lgput.out");

int main() {
    int base,power;
    long long result = 1;
    long long a;

    in >> base >> power;
    a = base;

    // mutam bitul de unu prin toate pozitiile
    for(int i=0;(1<<i) <= power;i++) {
        // prin "si" verificam daca bitul i
        // din reprezentarea binara a puterii este unu
        if( ((1<<i) & power) > 0)
            result = (result * a) % modulo;    // adaugam base^(2*i) la rezultat (wtf!?!)

        a = (a * a) % modulo;  // inmultim a cu a ca sa obtinem base^(2^(i+1)) (wtf!?!)
    }

    out << result;

    return (0);
}