#include <cstdio>
#include <algorithm>
#include <cstring>
#define mod 1999999973
using namespace std;
long long n, p;
long long lgput(long long a, long long b)
{
    if (b == 0)
        return 1;
    if (b == 1)
        return a;
    if (b % 2 == 0)
    {
        return lgput((a * a * 1LL) % mod, b / 2);
    }
    return (a * lgput(a, b - 1) * 1LL) % mod;
}
int main()
{
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);
    scanf("%lld %lld", &n, &p);
    printf("%lld", lgput(n, p));
    return 0;
}