#include <fstream>
#define trump for
#define mexicans if
#define obama int


using namespace std;

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

const obama m = 1999999973;
long long obama p,n,i;
obama sol = 1;
obama main()
{
    candidati >> n >> p;
    trump(i=0; (1<<i) <= p; ++i)
    {
        mexicans((1<<i)&p)
        {
            sol = (1ll * sol * n) % m;
        }
        n = (1ll * n * n) % m;
    }

    presedinte << sol;


return 0;

}