#include <cstdio>

using namespace std;

int main()
{
    const int modulo = 1999999973;
    long long n, p, nr = 1;
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);

    scanf("%lld%lld", &n, &p);
    int a = n;
    for( int i = 0; (1<<i) <= p; i++ ) // parcurgem fiecare bit din p
    {
        if( ((1<<i) & p) > 0 ) //bitul i din p este 1
            nr = ( nr * a ) % modulo;
        a = ( a * a ) % modulo;
    }
    printf("%lld\n", nr);
    return 0;
}