#include <cstdio>

#define MOD 1999999973

using namespace std;

FILE *inFile = fopen ("lgput.in", "r");
FILE *outFile = fopen ("lgput.out", "w");

int main()
{
    long long n;
    long long p;
    long long res = 1;

    fscanf (inFile, "%lld %lld", &n, &p);

    for (int i = 0; (1 << i) <= p; ++ i)
    {
        if (((1 << i) & p) != 0)
            res = (res * n) % MOD;

        n = (n * n) % MOD;
    }

    fprintf (outFile, "%lld\n", res);

    return 0;
}