#include<stdio.h>
#define MOD 1999999973

int p[40];

int main(){

    FILE *fin = fopen("lgput.in","r"),
         *fout = fopen("lgput.out","w");
         
    int A,B,sol=0;
    fscanf(fin,"%d%d",&A,&B);
    
    p[0] = A;
    for(int i=1;((long long)1<<i) <= (long long)B; i++)
        p[i] = (int)(((long long)p[i-1] * (long long)p[i-1])%(long long)MOD);

    for(int i=0;((long long)1<<i) <= (long long)B; i++)
        if( (1<<i) & B )
            sol = (int)(((long long)sol+p[i])%MOD);
            
    fprintf(fout,"%d\n",sol);
    
    fclose(fin);
    fclose(fout);
    return 0;

}