#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#include <bitset>
#include <list>
#include <algorithm>
#include <string>
using namespace std;

#define R 1999999973
unsigned int n, p;

unsigned int lgput(unsigned n, unsigned p)
{
    if (!p)
        return 1;
    else if (p == 1)
        return n % R;
    else
    {
        if ( n % 2 != 0 )
            return n * lgput((n * n) % R, (p-1)/2);
        else
            return lgput((n * n) % R, p/2);
    }
}
int main()
{
    ifstream f("lgput.in");
    ofstream g("lgput.out");
    f >> n >> p;

    g << lgput(n, p) % R;

    f.close();
    g.close();
    return 0;
}