#include <fstream>

using namespace std;

ifstream fin("lgput.in");
ofstream fout("lgput.out");

const int nmax=100, n2max=32, mod=1999999973;

typedef long long int64;

int64 v[nmax+1];

int u[n2max+1];

int main(){
    int64 n,m;
    fin>>n>>m;
    n%=mod;
    v[1]=n;
    for(int64 i=1,j=2;i<=m;i*=2,j++){
        n=n*n%mod;
        v[j]=n;
    }
    int p=0;
    while(m>0){
        p++;
        int m2=1,m3=0;
        while(m2*2<=m){
            m2*=2;
            m3++;
        }
        m-=m2;
        u[p]=m3+1;
    }
    int64 sum=0;
    for(int i=1;i<=p;i++){
        sum+=v[u[i]];
        sum%=mod;
    }
    fout<<sum<<"\n";
}