#include <stdio.h>
#define mod 1999999973

int bin[100], l;

void binar(int p)
{
    l = 0;
    while(p != 0)
    {
        bin[l++] = p % 2;
        p = p / 2;
    }
}

long long putere(int n, int p)
{
    int i;
    if(p == 0)
        return 1;
    if(p == 1)
        return n;
    long long r = n;
    for(i = l-2; i >= 0; i--)
    {
        if(bin[i] == 1)
            r = (r * r  * n) % mod;
        else
            r = (r * r) % mod;
       // printf("%d. %d r = %ull\n", l - i - 1, bin[i], r);
    }
    return r;
}

int main()
{
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);

    int n, p;

    scanf("%d %d", &n, &p);

    binar(p);
    printf("%lld", putere(n, p));


    binar(p);

    return 0;
}