#include<cstdio>
#include <vector>
#include <cstring>
/* #include "Euclid.cpp"
#include "EuclidExtended.cpp"
#include "LCS.cpp"
#include "RabinKarp.cpp"
#include "KMP.cpp"
#include "Arbint.cpp"
#include "Eratosthenes.cpp"
#include "Heap.cpp"
#include "Permutations.cpp"
 */
using namespace std;

#include <cstdio>
#include <cmath>

using namespace std;

class Lgpow {
#define MOD 1999999973

private:

    int N, P;
    long long p[33];

    void lgpow() {
        long long q = log2(P);

        p[0] = N;
        for (int i = 1; i <= q; i++)
            p[i] = (p[i - 1] * p[i - 1]) % MOD;
    }

public:
    void lgpow_main() {
        freopen("lgput.in", "r", stdin);
        freopen("lgput.out", "w", stdout);

        scanf("%d %d", &N, &P);

        long long ans = 1;

        lgpow();

        int k=0;
        while(P)
        {
            if(P&1)
                ans = ans*p[k]%MOD;
            ++k;
            P = P>>1;
        }

        printf("%d ",ans);
    }

} lgpow;

int main()
{
    lgpow.lgpow_main();
    return 0;
}