#include <fstream>
#include <cmath>
#include <algorithm>
#define nr 1999999973

using namespace std;
int n,d,k,p,i;

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

int main()
{
    fin >> n >> p;
    d =n*n%nr;
    k = 1;

    if(p%2)
        {
            for(i = 1; i < p/2; ++i)
                {
                    n *= d;
                    n%= nr;
                }
            fout << n;
        }
    else{ for(i = 1; i <= p/2; ++i)
            {
                k *= d;
                k%= nr;
            }
        fout << k;
    }



    return 0;
}