#include <stdio.h>
#include <stdlib.h>
#define MODULO 1999999973

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

int main (void)
{
    FILE *in,*out;
    long long n,p;
    if((in=fopen("lgput.in","r"))==NULL)
    {
        perror("fopen buba");
        exit(1);
    }
    if((out=fopen("lgput.out","w"))==NULL)
    {
        perror("fopen out buba");
        exit(1);
    }
    if(fscanf(in,"%lld %lld",&n,&p)!=2)
    {
        fprintf(stderr,"PUSCA SCRIEREA BAI");
        exit(1);
    }

    fprintf(out,"%lld",exp_log_rec(n,p)%MODULO);

    fclose(in);
    fclose(out);
    return 0;
}