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

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

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

int main()
{
    fin >> n >> p;
    for(i = 1; i <= p;i*=2,++putere)
    k = i;
    d = n;

    for(i = 1; i < putere; ++i)
        {
            n *= n;
            n %= nr;
        }

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






    return 0;
}