#include <cstdio>
#include <algorithm>
#define Mod 1999999973

using namespace std;
long long n,p;
long long putere(long long a, long long b)
{
    long long x;
    if (b == 0)
        return 1;
    x =  putere((a * a) % Mod, b / 2 );
    if (b % 2)
        x = (x * a) % Mod;

    return x;
}
int main()
{
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);
    scanf("%lld %lld",&n, &p);
    printf("%lld\n", putere(n, p));
    return 0;
}