#include<stdio.h>
#define MOD 1999999973

long long p[40];

int main(){

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

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

}