#include <iostream>
#define m 1999999973

using namespace std;

int n, p ;
long long sol = 1, a ;

int main()
{

    cin >> n >> p ;

    a = n ;

    for (int i = 0 ; (1 << i) <= p ; i ++)
    {

        if (((1 << i) & p) > 0)
            sol = (sol * a) % m ;

        a = (a * a) % m ;

    }

    cout << sol ;

    return 0 ;

}