#include <stdio.h>
#define M 1999999973

FILE *fin = NULL, *fout = NULL;
long long n , p;

long long exp_log_rec(long long x, long long n)
{
    if (n < 0)
        return (long long)exp_log_rec(1.0 / x, -n)%M;
    if (n == 0)
        return 1;
    if (n % 2 == 0)
        return (long long)exp_log_rec(x * x, n / 2)%M;
    else
        return (long long)(x * exp_log_rec(x * x, n / 2))%M;
}

int main()
{
    fin = fopen("lgput.in","r");
    fout = fopen("lgput.out","w");
    fscanf(fin,"%lld %lld",&n,&p);
    fprintf(fout,"%lld",exp_log_rec(n,p));
    fclose(fin);
    fclose(fout);
    return 0;
}