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

long long exp_log_rec(long long x,long long n) {
    if(n == 0) return 1;
    if(n % 2 == 0) 
    {
        return exp_log_rec((x*x)%MODULO, n/2);
    }
    else
    {
            return (x%MODULO) * exp_log_rec((x*x)%MODULO, 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,"fscanf");
        exit(1);
    }

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

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